QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167705#7179. Fischer's Chess Guessing Gameucup-team052#AC ✓91ms12784kbC++232.5kb2023-09-07 16:44:432023-09-07 16:44:43

Judging History

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

  • [2023-09-07 16:44:43]
  • 评测
  • 测评结果:AC
  • 用时:91ms
  • 内存:12784kb
  • [2023-09-07 16:44:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 1005
string s[N];
int n;
int _c[128];
int w[N][N];
void dfs(string cur)
{
	if(cur.length()==8)
	{
		int p1=-1,p2=-1,p=-1;
		for(int i=0;i<8;i++)
		{
			if(cur[i]=='R')
			{
				if(p1==-1) p1=i;
				else p2=i;
			}
			if(cur[i]=='K') p=i;
		}
		if(!(p1<p&&p<p2)) return ;
		p1=-1,p2=-1;
		for(int i=0;i<8;i++)
		{
			if(cur[i]=='B')
			{
				if(p1==-1) p1=i;
				else p2=i;
			}
		}
		if((p1&1)==(p2&1)) return ;
		s[n++]=cur;
	}
	if(_c['K']<1) _c['K']++,dfs(cur+"K"),_c['K']--;
	if(_c['Q']<1) _c['Q']++,dfs(cur+"Q"),_c['Q']--;
	if(_c['R']<2) _c['R']++,dfs(cur+"R"),_c['R']--;
	if(_c['B']<2) _c['B']++,dfs(cur+"B"),_c['B']--;
	if(_c['N']<2) _c['N']++,dfs(cur+"N"),_c['N']--;
}
#define M 500005
int q[M],ch[M][9],cnt,mxd,rt;
int solve(vector<int> v,int dep)
{
	int nw=++cnt; mxd=max(mxd,dep);
	if(v.size()==1) return -v[0];
	int mxx=inf,qry=-1;
	for(int i=0;i<n;i++)
	{
		vector<int> di[9];
		for(int j:v) di[w[i][j]].pb(j);
		int mx=0;
		for(int j=0;j<=8;j++) mx=max(mx,(int)di[j].size());
		if(mx<mxx) qry=i,mxx=mx;
	}
	q[nw]=qry;
	vector<int> di[9];
	for(int j:v) di[w[qry][j]].pb(j);
	for(int j=0;j<=8;j++) if(!di[j].empty()) ch[nw][j]=solve(di[j],dep+1);
	return nw;
}
void init()
{
	dfs("");
	for(int i=0;i<n;i++) for(int j=0;j<n;j++)
	{
		for(int k=0;k<8;k++) if(s[i][k]==s[j][k]) w[i][j]++;
		// printf("%d%c",w[i][j]," \n"[j==n-1]);
	}
	vector<int> v;
	for(int i=0;i<n;i++) v.pb(i);
	rt=solve(v,1);
	// cout<<mxd<<endl;
}
string ANS;
void qry(int u)
{
	if(u<=0) cout<<s[-u]<<endl;
	else cout<<s[q[u]]<<endl;
#ifdef wasa855
	string qr;
	if(u<=0) qr=s[-u];
	else qr=s[q[u]];
	int w=0;
	for(int i=0;i<8;i++) if(qr[i]==ANS[i]) w++;
#else
	int w=read();
#endif
	if(w==8) return ;
	qry(ch[u][w]);
}
void work()
{
	string s; cin>>s;
	if(s=="END") exit(0);
	read();
#ifdef wasa855
	cin>>ANS;
#endif
	qry(rt);
}
signed main()
{
	init();
	while(1) work();
	return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 81ms
memory: 10996kb

input:

GAME 1
4
3
3
2
8
END

output:

RQKBBNRN
RQKNBRNB
RKQNBNRB
QRKRBNNB
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 5 (1 test case)

Test #2:

score: 0
Accepted
time: 88ms
memory: 10832kb

input:

GAME 1
4
3
3
2
8
GAME 2
5
5
5
8
GAME 3
4
3
4
2
8
GAME 4
4
1
3
1
8
GAME 5
3
1
3
1
3
8
GAME 6
3
1
2
4
0
8
GAME 7
3
2
0
4
2
8
GAME 8
3
1
6
3
8
GAME 9
2
2
1
3
3
8
GAME 10
3
2
1
3
2
8
GAME 11
2
3
3
3
0
8
GAME 12
3
1
4
3
8
GAME 13
2
0
5
4
8
GAME 14
2
0
3
2
2
8
GAME 15
1
3
3
3
1
8
GAME 16
2
0
6
2
8
GAME 17...

output:

RQKBBNRN
RQKNBRNB
RKQNBNRB
QRKRBNNB
RKRBBQNN
RQKBBNRN
RKNRBNQB
RKNBBQRN
RKRBBNQN
RQKBBNRN
RQKNBRNB
RKQNBNRB
QRKRBBNN
RKRBBNNQ
RQKBBNRN
RQKNBRNB
RKBQRNNB
QRBNKNRB
RKRBQNBN
RQKBBNRN
NRQBBKNR
RKNRBBQN
QRKNBBRN
QRKRNBBN
RKRBNQBN
RQKBBNRN
NRQBBKNR
RKNRBBQN
QRKBNNBR
QRKRBBNN
RKRBNNBQ
RQKBBNRN
NRQBBKNR
QRB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #3:

score: 0
Accepted
time: 78ms
memory: 10768kb

input:

GAME 1
4
3
5
3
8
GAME 2
3
4
3
2
8
GAME 3
4
2
4
3
8
GAME 4
3
3
5
0
8
GAME 5
3
2
3
0
0
8
GAME 6
2
3
4
2
0
8
GAME 7
2
3
4
6
8
GAME 8
2
3
5
0
8
GAME 9
2
2
3
1
1
8
GAME 10
1
2
4
8
GAME 11
1
2
4
6
8
GAME 12
1
1
0
3
2
8
GAME 13
4
4
4
5
8
GAME 14
5
5
3
8
GAME 15
4
4
6
4
8
GAME 16
4
2
3
4
8
GAME 17
3
0
1
2
3...

output:

RQKBBNRN
RQKNBRNB
RKQNBNRB
QRKRBNNB
RKQBBNNR
RQKBBNRN
NRQBBKNR
QBNRBNKR
QRKRBBNN
RKNBBQNR
RQKBBNRN
RQKNBRNB
RNBBQNKR
QBRKBNNR
RKNBBNQR
RQKBBNRN
NRQBBKNR
QRKBNNBR
QRKRBBNN
RKQBNNBR
RQKBBNRN
NRQBBKNR
QRBBNNKR
QRBKNBRN
QRKRBBNN
RKNBQNBR
RQKBBNRN
NRKBBQNR
RQNBBKNR
RKQRBBNN
QRKRBBNN
RKNBNQBR
RQKBBNRN
NRK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #4:

score: 0
Accepted
time: 86ms
memory: 11080kb

input:

GAME 1
3
3
3
5
8
GAME 2
3
3
2
6
8
GAME 3
2
5
4
2
8
GAME 4
3
3
4
4
8
GAME 5
2
6
5
6
8
GAME 6
3
3
3
2
8
GAME 7
2
2
1
0
6
8
GAME 8
2
3
0
4
8
GAME 9
1
2
1
6
8
GAME 10
2
2
1
0
4
8
GAME 11
2
3
0
2
8
GAME 12
1
1
1
3
4
8
GAME 13
3
3
3
4
8
GAME 14
4
1
2
1
8
GAME 15
3
3
4
2
3
8
GAME 16
2
3
1
5
8
GAME 17
2
2
0...

output:

RQKBBNRN
NRQBBKNR
QRKBNNBR
QRKNRBBN
QRKRBBNN
RQKBBNRN
NRQBBKNR
QRKBNNBR
QRKRBBNN
NRKRBBQN
RQKBBNRN
NRKBBQNR
QRKRNBBN
QRKBRNBN
NRKRBBNQ
RQKBBNRN
NRQBBKNR
QRKBNNBR
QBRKBNNR
QRKRBNNB
RQKBBNRN
NRKBBQNR
QRKRBBNN
QRKRBNNB
NRKRBQNB
RQKBBNRN
NRQBBKNR
QRKBNNBR
QRKNRBBN
NRKRBNQB
RQKBBNRN
NRKBBQNR
QNNBBRKR
RBB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #5:

score: 0
Accepted
time: 90ms
memory: 10604kb

input:

GAME 1
3
0
2
0
2
8
GAME 2
2
0
2
1
2
8
GAME 3
1
3
2
4
1
8
GAME 4
3
0
0
1
8
GAME 5
2
0
3
4
1
8
GAME 6
1
2
4
2
8
GAME 7
2
1
4
3
2
8
GAME 8
2
0
3
0
1
8
GAME 9
1
4
0
2
8
GAME 10
3
3
0
1
8
GAME 11
3
1
5
1
8
GAME 12
2
2
3
6
8
GAME 13
2
0
4
1
3
8
GAME 14
2
0
4
1
2
8
GAME 15
1
3
4
3
2
8
GAME 16
2
1
3
1
1
8
G...

output:

RQKBBNRN
NRQBBKNR
BNRQKBRN
QRKRBNNB
QRKRBBNN
RQNKRBBN
RQKBBNRN
NRKBBQNR
RKNQNRBB
QBRNBKRN
QRKRBBNN
RNQKRBBN
RQKBBNRN
RNBBNKRQ
RBBNKRNQ
QNRKNBBR
QRKRBBNN
RNNKRBBQ
RQKBBNRN
NRQBBKNR
BNRQKBRN
QRKRNBBN
RQNKRNBB
RQKBBNRN
NRKBBQNR
RKNQNRBB
QRKNRNBB
QRKRNBBN
RNQKRNBB
RQKBBNRN
RNBBNKRQ
RKNNQRBB
RKQNNBBR
RNN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #6:

score: 0
Accepted
time: 82ms
memory: 11168kb

input:

GAME 1
2
1
1
4
8
GAME 2
2
2
0
2
5
8
GAME 3
1
4
3
3
8
GAME 4
2
1
1
6
8
GAME 5
2
2
0
1
3
8
GAME 6
1
3
1
0
8
GAME 7
3
2
2
3
5
8
GAME 8
3
4
1
3
8
GAME 9
2
3
2
1
3
8
GAME 10
3
2
3
4
3
8
GAME 11
3
4
2
1
8
GAME 12
2
4
0
2
8
GAME 13
0
2
6
2
8
GAME 14
0
1
3
6
8
GAME 15
0
2
5
1
8
GAME 16
0
3
1
4
4
8
GAME 17
0...

output:

RQKBBNRN
NRKBBQNR
RBBNKQNR
QRBKRNNB
QRBKNBRN
RQKBBNRN
NRKBBQNR
QNNBBRKR
QRKNNBBR
QRBKRBNN
NRBKQBRN
RQKBBNRN
RNBBNKRQ
NRQNBKRB
QRBKRNNB
NRBKNBRQ
RQKBBNRN
NRKBBQNR
RBBNKQNR
QRBKRNNB
QRBKNNRB
RQKBBNRN
NRKBBQNR
QNNBBRKR
QRKNNBBR
QRBKRBNN
NRBKQNRB
RQKBBNRN
RNBBNKRQ
RBBNKRNQ
BBQNRKNR
NRBKNQRB
RQKBBNRN
NRQ...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #7:

score: 0
Accepted
time: 80ms
memory: 10712kb

input:

GAME 1
2
1
5
3
8
GAME 2
2
0
2
3
1
8
GAME 3
1
3
8
GAME 4
2
0
3
2
1
8
GAME 5
2
0
5
2
0
8
GAME 6
1
2
5
4
1
8
GAME 7
4
4
1
8
GAME 8
3
1
3
1
1
8
GAME 9
2
2
3
5
8
GAME 10
2
1
5
4
8
GAME 11
1
3
5
1
8
GAME 12
1
3
5
2
8
GAME 13
4
3
1
0
8
GAME 14
3
2
1
1
1
8
GAME 15
2
1
2
0
0
8
GAME 16
2
0
5
1
8
GAME 17
1
2
5...

output:

RQKBBNRN
NRKBBQNR
RBBNKQNR
QRBKNRNB
RBBQKRNN
RQKBBNRN
NRKBBQNR
RKNQNRBB
QBRNBKRN
QRKNRNBB
RBBNKRQN
RQKBBNRN
RNBBNKRQ
RBBNKRNQ
RQKBBNRN
NRKBBQNR
RKNQNRBB
QRKNRNBB
QRKRBBNN
RBQNKRBN
RQKBBNRN
NRKBBQNR
RKNQNRBB
QRKRNBBN
QRKRBNNB
RBNQKRBN
RQKBBNRN
RNBBNKRQ
RKNNQRBB
QBRNKNBR
QRKBBRNN
RBNNKRBQ
RQKBBNRN
RQK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #8:

score: 0
Accepted
time: 78ms
memory: 10296kb

input:

GAME 1
2
3
3
3
3
8
GAME 2
2
4
5
2
8
GAME 3
1
1
0
2
1
8
GAME 4
0
4
1
3
8
GAME 5
0
3
3
2
8
GAME 6
0
2
3
5
8
GAME 7
1
0
4
0
3
8
GAME 8
1
0
5
0
8
GAME 9
0
3
4
0
8
GAME 10
3
2
1
2
2
8
GAME 11
2
1
1
0
1
8
GAME 12
1
3
4
2
1
8
GAME 13
1
0
4
1
2
8
GAME 14
0
1
2
1
8
GAME 15
0
2
0
0
8
GAME 16
1
0
6
2
8
GAME 17...

output:

RQKBBNRN
NRKBBQNR
RQNBBKNR
QRNKBRNB
QRKRNBBN
QRNBKNBR
RQKBBNRN
NRKBBQNR
QNRBKNBR
QRKRBNNB
NRQBKNBR
RQKBBNRN
RNBBNKRQ
QNRKBRNB
QRKNRBBN
QRKRBBNN
NRNBKQBR
RQKBBNRN
QBRNNKBR
BBQRNKNR
QRKRBBNN
QRNNKBBR
RQKBBNRN
QBRNNKBR
QNRNKRBB
QRBNNKRB
NRQNKBBR
RQKBBNRN
QBRNNKBR
QRBKNBNR
BRNNKBQR
NRNQKBBR
RQKBBNRN
RNB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #9:

score: 0
Accepted
time: 91ms
memory: 12784kb

input:

GAME 1
1
1
2
4
3
8
GAME 2
0
2
3
2
8
GAME 3
1
1
0
0
2
8
GAME 4
1
0
3
4
3
8
GAME 5
1
0
4
3
2
8
GAME 6
0
3
2
0
1
8
GAME 7
0
2
5
4
8
GAME 8
1
1
1
3
2
8
GAME 9
0
1
0
2
8
GAME 10
0
3
4
3
8
GAME 11
1
0
3
3
3
8
GAME 12
0
2
2
2
8
GAME 13
3
1
2
1
1
8
GAME 14
3
1
2
0
8
GAME 15
2
0
2
4
1
8
GAME 16
4
3
5
1
8
GAM...

output:

RQKBBNRN
RNBBNKRQ
QNRKBRNB
NBQRBNKR
QRKRBBNN
QBBRKNNR
RQKBBNRN
QBRNNKBR
QRBKNBNR
BRNNKBQR
NBBRKQNR
RQKBBNRN
RNBBNKRQ
QNRKBRNB
QRKNRBBN
QRBBKRNN
NBBRKNQR
RQKBBNRN
RNBBNKRQ
NBRNKRBQ
QRNNKRBB
QRKBRNBN
QBNRKNBR
RQKBBNRN
RNBBNKRQ
NBRNKRBQ
QRKRNNBB
QRKBRNBN
NBQRKNBR
RQKBBNRN
QBRNNKBR
QNRNKRBB
QRBKRBNN
QRK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #10:

score: 0
Accepted
time: 91ms
memory: 10672kb

input:

GAME 1
0
5
1
4
8
GAME 2
0
5
0
0
8
GAME 3
0
6
1
0
8
GAME 4
2
3
5
2
8
GAME 5
1
3
1
4
1
8
GAME 6
1
4
1
3
8
GAME 7
1
1
4
1
3
8
GAME 8
1
1
3
1
2
8
GAME 9
1
1
2
4
1
8
GAME 10
0
8
GAME 11
0
6
2
0
8
GAME 12
0
6
1
1
8
GAME 13
2
4
5
3
8
GAME 14
3
6
5
8
GAME 15
2
4
4
0
8
GAME 16
1
4
1
4
8
GAME 17
2
3
4
0
8
GAM...

output:

RQKBBNRN
QBRNNKBR
QRBKNBRN
QRBBNKNR
BBRQNKNR
RQKBBNRN
QBRNNKBR
QRBKNBRN
QRKBRNBN
BBRNQKNR
RQKBBNRN
QBRNNKBR
QRKRNBBN
QRKBRNBN
BBRNNKQR
RQKBBNRN
NRKBBQNR
RQNBBKNR
QNBBRKRN
BQRBNKNR
RQKBBNRN
RNBBNKRQ
RBBNKRNQ
BBQNRKNR
QRKRBNNB
BNRBQKNR
RQKBBNRN
RNBBNKRQ
NRQNBKRB
QBBRNKNR
BNRBNKQR
RQKBBNRN
RNBBNKRQ
QNR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #11:

score: 0
Accepted
time: 78ms
memory: 9736kb

input:

GAME 1
5
4
2
8
GAME 2
4
2
6
0
8
GAME 3
3
3
2
1
1
8
GAME 4
3
2
2
3
2
8
GAME 5
2
2
4
2
1
8
GAME 6
2
2
5
2
8
GAME 7
2
3
2
3
2
8
GAME 8
2
3
3
2
2
8
GAME 9
1
2
1
2
8
GAME 10
0
3
1
3
8
GAME 11
0
2
4
1
1
8
GAME 12
0
2
3
6
8
GAME 13
2
3
2
4
8
GAME 14
2
4
3
2
8
GAME 15
1
3
1
1
1
8
GAME 16
0
4
2
4
8
GAME 17
0...

output:

RQKBBNRN
RKNRBNQB
QRKRBNNB
RQNBBNKR
RQKBBNRN
RQKNBRNB
RNBBQNKR
QRKRNBBN
RNQBBNKR
RQKBBNRN
NRQBBKNR
QRKBNNBR
QRKRBBNN
QRKRBNNB
RNNBBQKR
RQKBBNRN
NRQBBKNR
QRBBNNKR
QRKNNBBR
QRKRBBNN
RQNNBBKR
RQKBBNRN
NRKBBQNR
QNNBBRKR
QRNKBBRN
QRKRBNNB
RNQNBBKR
RQKBBNRN
NRKBBQNR
QNNBBRKR
QRKRBBNN
RNNQBBKR
RQKBBNRN
NRK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Extra Test:

score: 0
Extra Test Passed