QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224152#7179. Fischer's Chess Guessing GamewxhtzdyAC ✓99ms8100kbC++202.5kb2023-10-23 00:11:162023-10-23 00:11:16

Judging History

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

  • [2023-10-23 00:11:16]
  • 评测
  • 测评结果:AC
  • 用时:99ms
  • 内存:8100kb
  • [2023-10-23 00:11:16]
  • 提交

answer

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int id,root,ncnt,ch[1000005][9],qq[1000005],ans[1000005];
string str[1005];

map<string,bool> val;
//map<int,string> str;

bool is_good(vector<char> f){
	int cnt=0;
	for(int i=0;i<f.size();i++){
		if(f[i]=='R') cnt++;
		if(f[i]=='K') if(cnt!=1) return false;
	}
	int s=0;
	for(int i=0;i<f.size();i++){
		if(f[i]=='B') s+=(i%2);
	}
	if(s!=1) return false;
	return true;
}

int solve(int x,int y){
	string a=str[x],b=str[y];
	int ret=0;
	for(int i=0;i<8;i++) ret+=(a[i]==b[i]?1:0);
	return ret;
}

void gen_vals(){
	vector<char> f;
	f.pb('K');
	f.pb('Q');
	f.pb('R');
	f.pb('R');
	f.pb('B');
	f.pb('B');
	f.pb('N');
	f.pb('N');
	vector<int> perm(8);
	for(int i=0;i<8;i++) perm[i]=i;
	do{
		vector<char> ff;
		for(int i=0;i<8;i++) ff.pb(f[perm[i]]);
		if(!is_good(ff)) continue;
		string s="";
		for(char c:ff) s+=c;
		if(!val[s]){
			val[s]=true;
			str[++id]=s;
		}
	} while(next_permutation(perm.begin(),perm.end()));
}

void dfs(int&nd,vector<int> v,int dep){
	if(v.empty()) return;
	assert(dep<=5);
	nd=++ncnt;
	assert(nd<=500000);
	int bst=1e9;
	for(int query=1;query<=id;query++){
		vector<int> cnt(9,0);
		for(int i:v) cnt[solve(query,i)]++;
		int mx=0;
		for(int i=0;i<8;i++) mx=max(mx,cnt[i]);
		if(bst>mx) bst=mx,qq[nd]=query;
	}
	assert(1<=qq[nd]&&qq[nd]<=id);
	if(dep==5) return;
	vector<vector<int>> gr(9);
	for(int i:v) gr[solve(qq[nd],i)].pb(i);
	for(int i=0;i<8;i++) dfs(ch[nd][i],gr[i],dep+1);
}

int final;

int diff(string a,string b){
	int ret=0;
	for(int i=0;i<8;i++) ret+=(a[i]==b[i]);
	return ret;
}

int prnt(string s){
	cout<<s<<endl;
	int x;
	cin>>x;
	return x;
}

void go(int nd,int dep){
	assert(dep<=6);
	int f=prnt(str[qq[nd]]);
	if(f==8) return;
	go(ch[nd][f],dep+1);
}

int main(){
	gen_vals();
	vector<int> vec;
	for(int i=1;i<=id;i++) vec.pb(i);
	dfs(root,vec,0);
	while(true){
		string s;
		cin>>s;
		if(s[0]=='E') break;
		if(s[0]=='G') cin>>s;
		go(root,1);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 92ms
memory: 7776kb

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: 94ms
memory: 8036kb

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: 96ms
memory: 7876kb

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: 99ms
memory: 7872kb

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: 94ms
memory: 8100kb

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: 91ms
memory: 7760kb

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: 86ms
memory: 7840kb

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: 88ms
memory: 7844kb

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: 95ms
memory: 7884kb

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: 83ms
memory: 7872kb

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: 86ms
memory: 7876kb

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