QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#173089 | #7179. Fischer's Chess Guessing Game | ucup-team298# | AC ✓ | 402ms | 6072kb | C++14 | 1.8kb | 2023-09-09 21:54:59 | 2023-09-09 21:55:00 |
Judging History
answer
#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
const int M=998244353;
inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
inline int Mod(re int x){return x>=M?x-M:x;}
inline int ksm(re int x,re int y){
re int s=1;
while(y){
if(y&1)s=1ll*s*x%M;
x=1ll*x*x%M,y>>=1;
}
return s;
}
int t,n,m,a[1000002],T[1002][12],tot,sz[12],mx,Tr[1002];
char s[12];
inline int Ask(re int x,re int y){
re int s=0;
for(re int i=1;i<=8;++i)s+=T[x][i]==T[y][i];
return s;
}
inline int Ask(re int x){
for(re int i=1;i<=8;++i)putchar(Tr[T[x][i]]);
puts("");fflush(stdout);return read();
}
inline void Solve(vector<int>A,re int dep){
mx=max(mx,dep);
if(A.size()<=1){
Ask(A[0]);
return;
}
re double MN=1e9;re int pos=0;
for(re int i=1;i<=tot;++i){
memset(sz,0,sizeof(sz));
for(auto z:A)++sz[Ask(z,i)];
double O=0;
for(re int j=0;j<=8;++j){
double P=1.0*sz[j]/A.size();
if(P>0)O+=P*log(P);
}
if(O<MN)MN=O,pos=i;
}
vector<int>Q[9];
for(auto z:A)Q[Ask(z,pos)].push_back(z);
int oo=Ask(pos);
if(oo==8)return;
Solve(Q[oo],dep+1);
}
int main(){
n=8;
a[1]=1,a[2]=1,a[3]=2,a[4]=2,a[5]=3,a[6]=3,a[7]=4,a[8]=5;
do{
int p1=0,p2=0,pos=0,ia=1;
for(re int i=1;i<=8;++i)
if(a[i]==1)
p1=p2,p2=i;
else if(a[i]==5)
pos=i;
if(pos<p1||pos>p2)ia=0;
for(re int i=1;i<=8;++i)
if(a[i]==3)
p1=p2,p2=i;
if((p1^p2)%2==0)ia=0;
if(ia){
++tot;
for(re int i=1;i<=8;++i)T[tot][i]=a[i];
}
}while(next_permutation(a+1,a+9));
while(1){
scanf("%s",s);
if(s[0]=='E')break;
t=read();
Tr[1]='R',Tr[2]='N',Tr[3]='B',Tr[4]='Q',Tr[5]='K';
vector<int>A;
for(re int i=1;i<=tot;++i)A.push_back(i);
Solve(A,0);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 3972kb
input:
GAME 1 4 1 4 4 8 END
output:
RNNBBQKR NRBBQNKR RNKBBRQN RBKNBQNR RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 395ms
memory: 3892kb
input:
GAME 1 4 1 4 4 8 GAME 2 3 3 2 1 3 8 GAME 3 3 3 3 3 4 8 GAME 4 2 2 3 3 8 GAME 5 3 3 1 3 2 8 GAME 6 2 3 1 2 4 8 GAME 7 2 3 3 2 4 8 GAME 8 2 5 3 2 8 GAME 9 2 4 2 3 3 8 GAME 10 2 2 2 0 2 8 GAME 11 3 6 2 1 8 GAME 12 2 4 2 3 2 8 GAME 13 1 2 3 1 3 8 GAME 14 1 4 4 1 8 GAME 15 1 2 1 0 8 GAME 16 1 1 0 4 1 8 G...
output:
RNNBBQKR NRBBQNKR RNKBBRQN RBKNBQNR RKRBBQNN RNNBBQKR RKNNBQRB RNKQBRNB RNNKQBBR RNNBBKRQ RKRBBNQN RNNBBQKR RKNNBQRB RNKQBRNB RNQBBKRN RNNBBKRQ RKRBBNNQ RNNBBQKR RKBNNBQR RNKNQRBB RKNQBNRB RKRBQNBN RNNBBQKR RKNNBQRB RNKQBRNB RBQKRNBN RNNBBKRQ RKRBNQBN RNNBBQKR RKBNNBQR RNBKQBRN QBBRNNKR RNNBKRBQ RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 389ms
memory: 4000kb
input:
GAME 1 4 3 5 3 8 GAME 2 6 3 5 8 GAME 3 5 3 2 4 8 GAME 4 3 2 2 1 2 8 GAME 5 4 4 6 8 GAME 6 5 2 4 2 8 GAME 7 3 4 8 GAME 8 4 1 2 3 8 GAME 9 4 1 3 4 8 GAME 10 2 6 1 8 GAME 11 3 3 2 5 8 GAME 12 3 4 5 2 8 GAME 13 3 3 4 6 8 GAME 14 2 2 2 1 2 8 GAME 15 2 1 3 2 2 8 GAME 16 1 4 2 1 8 GAME 17 2 2 3 1 1 8 GAME ...
output:
RNNBBQKR NRBBQNKR RNQBKNBR RNNBBKRQ RKQBBNNR RNNBBQKR RQKRBNNB RNNBKQBR RKNBBQNR RNNBBQKR NRBBQNKR RNBBQKRN RNNBBKRQ RKNBBNQR RNNBBQKR RKNNBQRB NRQNBBKR RNKNBBRQ RNNBBKRQ RKQBNNBR RNNBBQKR NRBBQNKR RNKBQNBR RKNBQNBR RNNBBQKR NRBBQNKR RQBBNKNR RNBNQBKR RKNBNQBR RNNBBQKR RKNNBQRB RKQNBBNR RNNBBQKR NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 391ms
memory: 4112kb
input:
GAME 1 1 1 4 2 1 8 GAME 2 1 1 5 3 8 GAME 3 1 0 1 4 8 GAME 4 1 0 1 3 8 GAME 5 2 0 4 1 8 GAME 6 1 0 2 0 8 GAME 7 0 3 2 4 8 GAME 8 0 4 4 1 8 GAME 9 0 4 3 0 8 GAME 10 0 5 4 8 GAME 11 0 6 4 8 GAME 12 1 0 3 3 0 8 GAME 13 2 0 0 1 8 GAME 14 1 1 6 1 8 GAME 15 1 0 0 0 8 GAME 16 0 4 4 0 8 GAME 17 0 3 4 0 8 GAM...
output:
RNNBBQKR RBBNQKRN BRKNRBQN RNKNBRQB RNNBBKRQ QRKRBBNN RNNBBQKR RBBNQKRN BRKNRBQN RNNKBBQR NRKRBBQN RNNBBQKR RBBNQKRN NNRQKRBB RNKBBRNQ NRKRBBNQ RNNBBQKR RBBNQKRN NNRQKRBB RNKBBRNQ QRKRBNNB RNNBBQKR RKBNNBQR NQNRBKRB RNQBBKRN NRKRBQNB RNNBBQKR RBBNQKRN NNRQKRBB RNNKRBBQ NRKRBNQB RNNBBQKR NRKQRNBB BRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 379ms
memory: 4272kb
input:
GAME 1 2 2 2 4 2 8 GAME 2 2 2 3 1 2 8 GAME 3 3 2 1 2 8 GAME 4 2 1 5 3 8 GAME 5 2 1 4 4 8 GAME 6 4 0 3 3 8 GAME 7 1 5 5 8 GAME 8 1 4 4 6 8 GAME 9 1 3 2 3 2 8 GAME 10 2 1 3 0 8 GAME 11 3 3 3 3 3 8 GAME 12 3 3 4 5 8 GAME 13 1 3 1 2 1 8 GAME 14 2 1 6 2 8 GAME 15 2 2 3 2 8 GAME 16 1 2 0 3 1 8 GAME 17 2 2...
output:
RNNBBQKR RKBNNBQR RNKNQRBB NQNRKBBR RNNBBKRQ RQNKRBBN RNNBBQKR RKBNNBQR RNKNQRBB RKNQBNRB RNNBBKRQ RNQKRBBN RNNBBQKR RKNNBQRB NRQNBBKR NBNRKQBR RNNKRBBQ RNNBBQKR RKBNNBQR RBNKQNBR RNNQBKRB RQNKRNBB RNNBBQKR RKBNNBQR RBNKQNBR RNQBKRBN RNQKRNBB RNNBBQKR NRBBQNKR RKBRNQNB RNNBBKRQ RNNKRQBB RNNBBQKR RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 402ms
memory: 4260kb
input:
GAME 1 0 1 2 0 8 GAME 2 0 2 3 1 8 GAME 3 0 2 4 3 8 GAME 4 0 3 2 2 8 GAME 5 0 4 4 4 8 GAME 6 1 2 2 6 8 GAME 7 2 1 2 1 3 8 GAME 8 1 2 4 1 2 8 GAME 9 2 1 2 1 4 8 GAME 10 2 0 4 2 8 GAME 11 1 1 1 4 0 8 GAME 12 3 5 2 1 8 GAME 13 1 0 0 1 8 GAME 14 2 2 1 4 3 8 GAME 15 2 4 6 1 8 GAME 16 1 1 2 1 8 GAME 17 1 2...
output:
RNNBBQKR NRKQRNBB BQRKNRNB RNNQKRBB QRBKNBRN RNNBBQKR NRKQRNBB QRBNNKRB BQRNKNRB NRBKQBRN RNNBBQKR NRKQRNBB QRBNNKRB RNQKNBBR NRBKNBRQ RNNBBQKR NRKQRNBB BRKNQRNB RNKRNQBB QRBKNNRB RNNBBQKR NRKQRNBB BRKRQNNB RNBNQKRB NRBKQNRB RNNBBQKR RBBNQKRN BRNQKBRN NRBKQNRB NRBKNQRB RNNBBQKR RKBNNBQR RBNKQNBR RBQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 388ms
memory: 3892kb
input:
GAME 1 1 4 4 3 8 GAME 2 1 5 4 1 8 GAME 3 1 4 2 5 8 GAME 4 1 4 2 4 1 8 GAME 5 2 1 4 5 8 GAME 6 2 2 4 5 3 8 GAME 7 2 2 2 2 4 8 GAME 8 3 1 0 6 8 GAME 9 3 1 0 5 8 GAME 10 1 3 4 2 8 GAME 11 2 2 4 1 8 GAME 12 2 4 3 5 8 GAME 13 3 2 0 1 8 GAME 14 3 1 0 4 8 GAME 15 4 1 4 1 8 GAME 16 2 2 5 1 8 GAME 17 2 2 6 5...
output:
RNNBBQKR RBBNQKRN RKBQNBRN RNBKNRQB RBBQKRNN RNNBBQKR RBBNQKRN RKBNQRNB RNNBQKBR RBBNKRQN RNNBBQKR RBBNQKRN RKBQNBRN RNBNKRQB RBBNKRNQ RNNBBQKR RBBNQKRN RKBQNBRN RNBNKRQB RNNBBKRQ RBQNKRBN RNNBBQKR RKBNNBQR RBNKQNBR RNQBKRBN RBNQKRBN RNNBBQKR RKBNNBQR RNKNQRBB RBKNRNBQ RNNBQKBR RBNNKRBQ RNNBBQKR RKB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 391ms
memory: 4024kb
input:
GAME 1 3 1 3 4 8 GAME 2 2 1 3 6 3 8 GAME 3 4 4 3 4 8 GAME 4 2 3 1 2 3 8 GAME 5 1 1 3 1 2 8 GAME 6 2 2 1 8 GAME 7 0 1 4 3 8 GAME 8 0 0 3 2 8 GAME 9 0 0 5 1 8 GAME 10 1 1 2 2 8 GAME 11 2 1 0 1 3 8 GAME 12 2 0 0 3 8 GAME 13 0 1 6 8 GAME 14 1 0 6 2 8 GAME 15 1 1 3 1 3 8 GAME 16 0 1 2 3 8 GAME 17 0 3 1 0...
output:
RNNBBQKR RKNNBQRB BBNQRNKR NRNBBKQR QRNBKNBR RNNBBQKR RKBNNBQR RBNKQNBR NRKBQNBR RNNBKRBQ NRQBKNBR RNNBBQKR NRBBQNKR RNKBQNBR RNNBKRBQ NRNBKQBR RNNBBQKR RKBNNBQR RNBKQBRN QBBRNNKR RNNBKRBQ QRNNKBBR RNNBBQKR RBBNQKRN BRKNRBQN BRKBNNRQ RNNBKRBQ NRQNKBBR RNNBBQKR RKBNNBQR RNKNQRBB NRNQKBBR RNNBBQKR NRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 390ms
memory: 4264kb
input:
GAME 1 1 2 1 8 GAME 2 2 2 0 2 3 8 GAME 3 1 2 1 6 8 GAME 4 2 1 5 1 8 GAME 5 1 1 0 6 8 GAME 6 3 2 2 0 8 GAME 7 2 3 3 0 8 GAME 8 1 1 1 0 0 8 GAME 9 2 4 4 4 8 GAME 10 3 1 2 1 8 GAME 11 2 2 1 6 8 GAME 12 2 2 2 6 8 GAME 13 1 6 2 8 GAME 14 1 8 GAME 15 1 6 1 8 GAME 16 2 2 2 0 4 8 GAME 17 3 4 2 2 8 GAME 18 3...
output:
RNNBBQKR RBBNQKRN BRNQKBRN QBBRKNNR RNNBBQKR RKBNNBQR RNKNQRBB BBRQNNKR RNBNKQRB NBBRKQNR RNNBBQKR RBBNQKRN BRNQKBRN QBBRKNNR NBBRKNQR RNNBBQKR RKBNNBQR RBNKQNBR RNNQBKRB QBNRKNBR RNNBBQKR RBBNQKRN BRKNRBQN NBRQKNBR NBQRKNBR RNNBBQKR RKNNBQRB NRQNBBKR RNKNBBRQ NBNRKQBR RNNBBQKR RKBNNBQR RNBKQBRN RBK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 387ms
memory: 4140kb
input:
GAME 1 1 2 2 0 1 8 GAME 2 1 4 0 3 8 GAME 3 1 3 2 5 2 8 GAME 4 2 2 0 4 3 8 GAME 5 3 0 1 3 8 GAME 6 3 0 2 2 5 8 GAME 7 2 2 1 1 2 8 GAME 8 2 1 2 5 8 GAME 9 2 3 0 3 8 GAME 10 1 3 1 3 8 GAME 11 1 2 1 2 3 8 GAME 12 1 4 0 4 8 GAME 13 4 2 1 1 8 GAME 14 3 1 1 1 2 8 GAME 15 4 3 3 2 8 GAME 16 3 0 2 3 8 GAME 17...
output:
RNNBBQKR RBBNQKRN BRNQKBRN NRBKQNRB RNQNBBKR BBRQNKNR RNNBBQKR RBBNQKRN RKBQNBRN RNNBQKBR BBRNQKNR RNNBBQKR RBBNQKRN RKBNRNQB BBQRNKNR RNBBNQKR BBRNNKQR RNNBBQKR RKBNNBQR RNKNQRBB BBRQNNKR RNNBQKBR BQRBNKNR RNNBBQKR RKNNBQRB NQBRNBKR RNQBKNBR BNRBQKNR RNNBBQKR RKNNBQRB NQBRNBKR RKRNNBBQ RNNBBKQR BNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 366ms
memory: 6072kb
input:
GAME 1 6 4 4 8 GAME 2 6 3 4 8 GAME 3 8 GAME 4 5 2 3 8 GAME 5 5 2 2 8 GAME 6 6 2 4 8 GAME 7 3 0 3 1 8 GAME 8 4 6 1 8 GAME 9 5 4 0 8 GAME 10 2 4 5 0 8 GAME 11 3 1 5 4 8 GAME 12 3 2 5 1 8 GAME 13 3 0 4 5 8 GAME 14 3 0 4 6 8 GAME 15 4 6 4 8 GAME 16 2 5 1 0 8 GAME 17 2 4 3 2 8 GAME 18 2 4 4 1 8 GAME 19 5...
output:
RNNBBQKR RQKRBNNB RNNBKQBR RQNBBNKR RNNBBQKR RQKRBNNB RNNBKQBR RNQBBNKR RNNBBQKR RNNBBQKR NRBBQNKR RQBBNKNR RQNNBBKR RNNBBQKR NRBBQNKR RQBBNKNR RNQNBBKR RNNBBQKR RQKRBNNB RNNBBKRQ RNNQBBKR RNNBBQKR RKNNBQRB NQBRNBKR RNNBBKRQ BRQBNNKR RNNBBQKR NRBBQNKR NRBKNRQB BRNBQNKR RNNBBQKR NRBBQNKR NQRKBRNB BRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed