QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#175807#7179. Fischer's Chess Guessing Gameucup-team1231#AC ✓972ms3680kbC++142.2kb2023-09-11 00:29:332023-09-11 00:29:34

Judging History

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

  • [2023-09-11 00:29:34]
  • 评测
  • 测评结果:AC
  • 用时:972ms
  • 内存:3680kb
  • [2023-09-11 00:29:33]
  • 提交

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