QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#173089#7179. Fischer's Chess Guessing Gameucup-team298#AC ✓402ms6072kbC++141.8kb2023-09-09 21:54:592023-09-09 21:55:00

Judging History

你现在查看的是最新测评结果

  • [2023-09-09 21:55:00]
  • 评测
  • 测评结果:AC
  • 用时:402ms
  • 内存:6072kb
  • [2023-09-09 21:54:59]
  • 提交

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