QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#175807 | #7179. Fischer's Chess Guessing Game | ucup-team1231# | AC ✓ | 972ms | 3680kb | C++14 | 2.2kb | 2023-09-11 00:29:33 | 2023-09-11 00:29:34 |
Judging History
answer
#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
set<string> ok;
int diff(const string& a,const string& b) {
int d=0;
for(int i=0;i<a.size();++i)
d+=a[i]==b[i];
return d;
}
void test(string s) {
set<string> cand=ok;
for(int i=1;i<=6;++i) {
int best=2e9; string qq;
for(auto k:ok) {
map<int,int> c;
for(auto w:cand) ++c[diff(k,w)];
int ms=0;
for(auto t:c) ms+=t.second*t.second;
if(ms<best) best=ms, qq=k;
}
int qry_rst=diff(s,qq);
set<string> ns;
for(auto w:cand) if(diff(w,qq)==qry_rst) ns.insert(w);
cand=ns;
assert(cand.count(s));
cout<<cand.size()<<",";
}
cout<<"\n";
assert(cand.size()==1);
}
int main() {
string P="RQKBBNRN";
sort(P.begin(),P.end());
do {
int s=P.find('K');
set<int> c;
for(int t=0;t<P.size();++t) if(P[t]=='B') c.insert(t%2);
int l=0,r=0;
for(int t=s;t>=0;--t) l|=P[t]=='R';
for(int t=s;t<P.size();++t) r|=P[t]=='R';
if(l&&r&&c.size()==2) ok.insert(P);
}while(next_permutation(P.begin(),P.end()));
while(1) {
string op; cin>>op;
if(op=="END") break;
assert(op=="GAME"); int t; cin>>t;
vector<string> cand(ok.begin(),ok.end());
for(;;) {
int best=2e9; string qq;
for(auto k:ok) {
static int c[10];
memset(c,0,sizeof c);
for(auto w:cand) ++c[diff(k,w)];
int ms=0;
for(auto t:c) ms+=t*t;
if(ms<best) best=ms, qq=k;
}
if(cand.size()==1) qq=*cand.begin();
int qry_rst;
cout<<qq<<endl;
cin>>qry_rst;
if(qry_rst==8) break;
vector<string> ns;
for(auto w:cand) if(diff(w,qq)==qry_rst) ns.push_back(w);
cand=ns;
// cerr<<"cand size"<<cand.size()<<"?\n";
}
}
/*
cout<<ok.size()<<"\n";
for(auto w:ok) {
cout<<w<<"+++\n";
test(w);
}*/
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 3600kb
input:
GAME 1 2 2 1 0 8 END
output:
NRBBNQKR RBBNQKNR RQNKNBBR QRBNNKRB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 962ms
memory: 3668kb
input:
GAME 1 2 2 1 0 8 GAME 2 1 2 1 1 1 8 GAME 3 1 3 4 0 8 GAME 4 1 3 2 0 0 8 GAME 5 3 2 3 8 GAME 6 2 1 3 1 0 8 GAME 7 0 5 5 8 GAME 8 0 3 5 1 8 GAME 9 0 4 5 1 8 GAME 10 0 6 0 8 GAME 11 1 4 3 2 8 GAME 12 0 4 4 0 8 GAME 13 1 3 1 1 0 8 GAME 14 0 2 3 0 8 GAME 15 1 4 2 0 8 GAME 16 1 2 0 6 8 GAME 17 0 3 3 4 8 G...
output:
NRBBNQKR RBBNQKNR RQNKNBBR QRBNNKRB RKRBBQNN NRBBNQKR RKBNQBNR BRKNQBRN NBQRKNBR BBNQRKRN RKRBBNQN NRBBNQKR RKBNQBNR QBRKBNNR BBNQNRKR RKRBBNNQ NRBBNQKR RKBNQBNR QBRKBNNR BBNRKQNR BBNNRKRQ RKRBQNBN NRBBNQKR RNQBBNKR RBBKNQNR RKRBNQBN NRBBNQKR RBBNQKNR BRKBNRNQ NRKNRQBB BBNNQRKR RKRBNNBQ NRBBNQKR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 956ms
memory: 3624kb
input:
GAME 1 2 3 4 0 8 GAME 2 3 4 5 2 8 GAME 3 2 2 3 4 8 GAME 4 3 5 5 8 GAME 5 2 3 3 5 8 GAME 6 4 2 2 1 8 GAME 7 1 6 1 2 8 GAME 8 1 5 4 8 GAME 9 1 5 3 8 GAME 10 2 3 3 6 8 GAME 11 2 2 6 2 8 GAME 12 1 6 0 8 GAME 13 1 2 2 3 1 8 GAME 14 0 2 4 0 1 8 GAME 15 0 3 3 1 8 GAME 16 0 1 2 0 8 GAME 17 2 2 3 3 2 8 GAME ...
output:
NRBBNQKR RBBNQKNR RKBBNRNQ BBNRNKRQ RKQBBNNR NRBBNQKR RNQBBNKR RKBBQNNR BBNNQRKR RKNBBQNR NRBBNQKR RBBNQKNR RQNKNBBR RKBBNRQN RKNBBNQR NRBBNQKR RNQBBNKR RKBBNNRQ RKQBNNBR NRBBNQKR RBBNQKNR RKBBNRNQ RKNQNBBR RKNBQNBR NRBBNQKR BBNRQNKR NRKBBNQR BBQNRNKR RKNBNQBR NRBBNQKR RKBNQBNR NQBRKRNB BBNNRKQR RKQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 944ms
memory: 3664kb
input:
GAME 1 1 2 4 0 8 GAME 2 2 0 4 4 8 GAME 3 2 1 4 2 0 8 GAME 4 1 1 0 2 0 8 GAME 5 3 1 3 0 0 8 GAME 6 2 0 2 1 8 GAME 7 2 0 5 0 8 GAME 8 2 1 2 6 8 GAME 9 3 0 3 1 8 GAME 10 2 0 3 5 0 8 GAME 11 2 1 2 5 1 8 GAME 12 4 1 0 8 GAME 13 3 1 6 2 8 GAME 14 2 0 4 1 8 GAME 15 2 1 6 1 8 GAME 16 1 2 5 4 8 GAME 17 1 2 6...
output:
NRBBNQKR RKBNQBNR BRKNQBRN BBNNRKRQ QRKRBBNN NRBBNQKR RBBNQKNR BRKQNBRN NQRKBBRN NRKRBBQN NRBBNQKR RBBNQKNR BRKBNRNQ BRKNQNRB BBNNQRKR NRKRBBNQ NRBBNQKR RKBNQBNR NBRKNRBQ QNRBBKRN BBNNQRKR QRKRBNNB NRBBNQKR RNQBBNKR BRKBNQRN BBRKNNRQ BBNNQRKR NRKRBQNB NRBBNQKR RBBNQKNR BRKQNBRN QRNKNBBR NRKRBNQB NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 927ms
memory: 3660kb
input:
GAME 1 0 2 5 1 8 GAME 2 0 1 1 0 8 GAME 3 0 2 4 6 8 GAME 4 0 3 2 2 8 GAME 5 0 2 6 1 8 GAME 6 1 1 2 2 2 8 GAME 7 1 4 2 2 8 GAME 8 2 3 4 2 8 GAME 9 2 4 2 1 8 GAME 10 0 4 4 2 8 GAME 11 0 4 3 1 8 GAME 12 0 5 2 3 8 GAME 13 1 1 5 1 8 GAME 14 0 3 2 5 8 GAME 15 1 1 6 3 2 8 GAME 16 2 3 5 1 8 GAME 17 1 4 3 1 2...
output:
NRBBNQKR RKNQBRNB RBQKRNBN BBNQNRKR RQNKRBBN NRBBNQKR RKNQBRNB BNNRQKRB BBRNKNQR RNQKRBBN NRBBNQKR RKNQBRNB RBQKRNBN NNRKRBBQ RNNKRBBQ NRBBNQKR RKNQBRNB RKNNBBRQ RBQNKRBN RQNKRNBB NRBBNQKR RKNQBRNB RBQKRNBN BBNRKNRQ RNQKRNBB NRBBNQKR RKBNQBNR NBRKNRBQ BNRBKQRN BBNRKQRN RNNKRQBB NRBBNQKR RKBNQBNR QNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 944ms
memory: 3580kb
input:
GAME 1 3 0 2 3 8 GAME 2 3 0 1 0 8 GAME 3 4 0 2 2 8 GAME 4 3 1 3 4 8 GAME 5 3 1 2 5 8 GAME 6 5 0 1 8 GAME 7 1 1 1 3 1 8 GAME 8 2 0 4 6 8 GAME 9 2 0 3 1 1 8 GAME 10 1 0 3 5 8 GAME 11 2 0 2 2 8 GAME 12 3 1 3 2 1 8 GAME 13 3 2 4 2 8 GAME 14 2 3 1 3 3 8 GAME 15 3 1 3 3 8 GAME 16 4 1 3 1 8 GAME 17 4 2 3 2...
output:
NRBBNQKR RNQBBNKR BRKNNRQB BNRKRBQN QRBKNBRN NRBBNQKR RNQBBNKR BRKNNRQB BBNRKRNQ NRBKQBRN NRBBNQKR BBNRQNKR NRKNRQBB BBNNRKRQ NRBKNBRQ NRBBNQKR RNQBBNKR BRKBNQRN BBRKNNRQ QRBKNNRB NRBBNQKR RNQBBNKR BRKBNQRN NNBRQKRB NRBKQNRB NRBBNQKR BBQNRNKR BBNRKQNR NRBKNQRB NRBBNQKR RKBNQBNR NBRKNRBQ BRNKNRQB BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 938ms
memory: 3616kb
input:
GAME 1 1 3 2 3 2 8 GAME 2 1 3 1 4 8 GAME 3 1 4 1 3 8 GAME 4 0 2 5 2 8 GAME 5 0 4 2 4 8 GAME 6 0 3 4 1 8 GAME 7 2 3 5 3 8 GAME 8 2 2 1 1 1 8 GAME 9 2 3 6 3 8 GAME 10 1 4 1 2 1 8 GAME 11 1 3 1 5 1 8 GAME 12 1 3 0 1 8 GAME 13 1 1 2 3 1 8 GAME 14 1 1 2 4 0 8 GAME 15 1 1 3 4 8 GAME 16 0 4 2 2 8 GAME 17 0...
output:
NRBBNQKR RKBNQBNR QBRKBNNR BBNRKQNR BBNNQRKR RBBQKRNN NRBBNQKR RKBNQBNR QBRKBNNR RNBNKQRB RBBNKRQN NRBBNQKR RKBNQBNR QNRKBBNR BBNNQRKR RBBNKRNQ NRBBNQKR RKNQBRNB RBQKRNBN BBNQNRKR RBQNKRBN NRBBNQKR RKNQBRNB RKQNBBRN BBNQNRKR RBNQKRBN NRBBNQKR RKNQBRNB RKNNBBRQ NRKNBQRB RBNNKRBQ NRBBNQKR RBBNQKNR RKB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 972ms
memory: 3600kb
input:
GAME 1 3 3 1 2 8 GAME 2 4 2 5 1 8 GAME 3 5 1 2 8 GAME 4 2 2 4 6 8 GAME 5 3 2 1 4 2 8 GAME 6 3 1 1 5 8 GAME 7 0 3 0 4 8 GAME 8 0 1 1 6 8 GAME 9 0 2 1 6 8 GAME 10 1 1 2 5 8 GAME 11 1 0 1 2 8 GAME 12 1 1 3 5 8 GAME 13 0 3 1 4 8 GAME 14 0 4 0 2 8 GAME 15 0 2 0 2 8 GAME 16 0 1 0 3 8 GAME 17 1 0 0 2 8 GAM...
output:
NRBBNQKR RNQBBNKR BQRNNBKR BBNRQKNR QRNBKNBR NRBBNQKR BBNRQNKR NRKBBNQR BBNQNRKR NRQBKNBR NRBBNQKR BBQNRNKR BNRBQKNR NRNBKQBR NRBBNQKR RBBNQKNR RQNKNBBR BRNNKBQR QRNNKBBR NRBBNQKR RNQBBNKR RBBKNQNR BRKNNBQR BBNNQRKR NRQNKBBR NRBBNQKR RNQBBNKR BRKBNQRN NBNRKQBR NRNQKBBR NRBBNQKR RKNQBRNB RKNNBBRQ BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 958ms
memory: 3608kb
input:
GAME 1 2 4 3 4 8 GAME 2 4 3 1 2 8 GAME 3 3 2 3 0 8 GAME 4 1 1 2 1 3 8 GAME 5 2 2 2 4 2 8 GAME 6 3 1 1 8 GAME 7 2 3 2 3 8 GAME 8 3 1 0 1 8 GAME 9 3 2 2 5 8 GAME 10 1 2 1 4 2 8 GAME 11 2 1 0 8 GAME 12 2 1 0 6 8 GAME 13 2 4 3 2 1 8 GAME 14 1 4 0 3 8 GAME 15 2 5 3 2 8 GAME 16 0 2 4 0 2 8 GAME 17 0 4 4 6...
output:
NRBBNQKR RBBNQKNR NBQRNKBR RBQKBNNR QBBRKNNR NRBBNQKR BBNRQNKR BRNBNKQR BBNNQRKR NBBRKQNR NRBBNQKR RNQBBNKR RBBKNQNR RKRBNQBN NBBRKNQR NRBBNQKR RKBNQBNR NBRKNRBQ BNRBKQRN BBNQNRKR QBNRKNBR NRBBNQKR RBBNQKNR RQNKNBBR NBRQBNKR BBNNQRKR NBQRKNBR NRBBNQKR RNQBBNKR BRKBNQRN NBNRKQBR NRBBNQKR RBBNQKNR RKB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 931ms
memory: 3608kb
input:
GAME 1 2 4 4 4 8 GAME 2 1 4 3 6 8 GAME 3 2 4 4 6 8 GAME 4 3 2 3 3 8 GAME 5 2 4 2 5 8 GAME 6 3 3 4 5 8 GAME 7 1 3 6 3 8 GAME 8 2 4 4 3 8 GAME 9 2 4 4 5 8 GAME 10 2 4 5 3 8 GAME 11 3 1 1 4 2 8 GAME 12 2 5 2 8 GAME 13 2 3 2 6 8 GAME 14 3 3 3 3 8 GAME 15 3 4 2 1 8 GAME 16 3 3 3 2 1 8 GAME 17 4 1 3 3 8 G...
output:
NRBBNQKR RBBNQKNR NBQRNKBR BBNNRKQR BBRQNKNR NRBBNQKR RKBNQBNR QNRKBBNR NBRNQKBR BBRNQKNR NRBBNQKR RBBNQKNR NBQRNKBR BBNNRKQR BBRNNKQR NRBBNQKR RNQBBNKR RBBKNQNR RKRBNQBN BQRBNKNR NRBBNQKR RBBNQKNR NBQRNKBR BNNBQRKR BNRBQKNR NRBBNQKR RNQBBNKR BQRNNBKR BBNRNKQR BNRBNKQR NRBBNQKR RKBNQBNR QBRKBNNR BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 854ms
memory: 3680kb
input:
GAME 1 3 6 2 8 GAME 2 3 8 GAME 3 4 3 3 6 8 GAME 4 2 3 1 3 4 8 GAME 5 2 3 1 2 2 8 GAME 6 2 2 4 3 8 GAME 7 5 5 3 8 GAME 8 4 6 3 8 GAME 9 6 5 8 GAME 10 4 3 4 3 8 GAME 11 4 4 5 3 8 GAME 12 3 2 1 5 8 GAME 13 6 3 2 8 GAME 14 6 2 2 8 GAME 15 8 GAME 16 5 3 4 8 GAME 17 6 4 0 8 GAME 18 5 3 6 8 GAME 19 4 4 4 3...
output:
NRBBNQKR RNQBBNKR BBNNRKQR RQNBBNKR NRBBNQKR RNQBBNKR NRBBNQKR BBNRQNKR BRNBNKQR BNNBRQKR RNNBBQKR NRBBNQKR RBBNQKNR RKBBNRNQ BBNRNQKR BBNNRQKR RQNNBBKR NRBBNQKR RBBNQKNR RKBBNRNQ BBNRNQKR BBNNRKQR RNQNBBKR NRBBNQKR RBBNQKNR RQNKNBBR BRNNKBQR RNNQBBKR NRBBNQKR BBQNRNKR BBNNQRKR BRQBNNKR NRBBNQKR BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed