QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345299#7179. Fischer's Chess Guessing GameinstallbAC ✓178ms4028kbC++142.9kb2024-03-06 19:16:012024-03-06 19:16:01

Judging History

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

  • [2024-03-06 19:16:01]
  • 评测
  • 测评结果:AC
  • 用时:178ms
  • 内存:4028kb
  • [2024-03-06 19:16:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const int N = 800005;

vector <string> G,iG;
map <string,int> mp; int tot = 0;

void init1(){
    string s = "BBKNNQRR";
    do{
        int pk; vector <int> pb,pr;
        for(int i = 0;i < 8;i ++){
            if(s[i] == 'B') pb.push_back(i);
            if(s[i] == 'R') pr.push_back(i);
            if(s[i] == 'K') pk = i;
        }
        if((pb[0] & 1) == (pb[1] & 1)) continue;
        if(!(pr[0] < pk && pk < pr[1])) continue;
        if(mp.find(s) != mp.end()) continue;
        mp[s] = tot ++;
        G.push_back(s);
    }while(next_permutation(s.begin(),s.end()));
}

mt19937 rnd(998244353);
string SS;

int calc(string x,string y){ int r = 0; for(int i = 0;i < 8;i ++) if(x[i] == y[i]) r ++; return r; }

void solve(){
    vector <string> H;
    G = iG;
    string lis[6];
    for(int ti = 0;ti < 5;ti ++){
        if(G.size() == 1) break;
        string cur;
        bool flg = 0;
        for(auto &x:G) if(x=="RQNKRBBN") flg = 1;
		if(ti > 0){
            if(!flg){
                db anss = 0;
                for(int x = 0;x < G.size();x ++){
                    map <int,int> chk;
                    for(int i = 0;i < G.size();i ++) chk[calc(G[i],G[x])] ++;
                    db mx = 0;
                    for(auto it = chk.begin();it != chk.end();it ++){
                        db val = 1.0 * it->second / G.size();
                        mx += val * log2(1.0 / val);
                    }
                    if(mx > anss){
                        anss = mx;
                        cur = G[x];
                    }
                }
            }else{
                int anss = 1e9;
                for(int x = 0;x < G.size();x ++){
                    map <int,int> chk;
                    for(int i = 0;i < G.size();i ++) chk[calc(G[i],G[x])] ++;
                    int mx = 0;
                    for(auto it = chk.begin();it != chk.end();it ++) mx = max(mx,it->second);
                    if(mx < anss){
                        anss = mx;
                        cur = G[x];
                    }
                }
            }
		}else{
			cur = "RBBNNQKR";
		}
        cout << cur << endl;
        int x;
        cin >> x;
        // x = calc(cur,SS);
        if(x == 8) return;
        for(int i = 0;i < G.size();i ++) if(calc(cur,G[i]) == x) H.push_back(G[i]);
        G.swap(H); H.clear();
        lis[ti] = cur;
    }
    cout << G[0] << endl;
    int x;
    cin >> x;
    // x = calc(SS,G[0]);
    // if(x != 8) cout << SS << endl;
}


int main(){
    ios::sync_with_stdio(false);
    init1();
    iG = G;
    // for(auto s : iG){
        // SS = s; solve();
    // }
    string str;
    while(cin >> str){
        if(str == "END") break;
        int x; cin >> x;
        // cin >> SS;
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 3676kb

input:

GAME 1
2
3
1
1
0
8
END

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RQKNRNBB
BBNRKNQR
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 165ms
memory: 3816kb

input:

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

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RQKNRNBB
BBNRKNQR
RKRBBQNN
RBBNNQKR
RNQBBKRN
BNQNRKRB
RKNBBRQN
RKRBBNQN
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RKRBBNNQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
NBNRBKRQ
RKRBQNBN
RBBNNQKR
RKBNQBRN
RKBQNRNB
RKRBNQBN
RBBNNQKR
RKNBQNBR
RKNNQRBB
RKBBQNRN
RKRBNNBQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RNKRBBNQ
RKN...

result:

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

Test #3:

score: 0
Accepted
time: 169ms
memory: 3820kb

input:

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

output:

RBBNNQKR
RKNBQNBR
RKNNQRBB
RKQBBNNR
RBBNNQKR
RKBNQBRN
QRNNBBKR
RQNKNBBR
RKNBBQNR
RBBNNQKR
RKNBQNBR
RNKBQNBR
RKNBBNQR
RBBNNQKR
RKBNQBRN
QRNNBBKR
RNKNRQBB
RKQBNNBR
RBBNNQKR
RKNBQNBR
RBBNNQKR
BBRNQNKR
RQBBNKNR
RBBQNKRN
RKNBNQBR
RBBNNQKR
RKBNQBRN
RKBQNNRB
RBBKQRNN
RKQNBBNR
RBBNNQKR
RKNBQNBR
RKNQNRBB
RNN...

result:

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

Test #4:

score: 0
Accepted
time: 167ms
memory: 3972kb

input:

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

output:

RBBNNQKR
QNRKBNRB
BNQRKRNB
BNNBRKRQ
NRKRQNBB
QRKRBBNN
RBBNNQKR
QNRKBNRB
NRKBRNBQ
NQRBKRBN
NRKRBBQN
RBBNNQKR
QNRKBNRB
NRKBRNBQ
NRKBBRQN
NRKRBBNQ
RBBNNQKR
QNRKBNRB
BNRKQRNB
NNRBBKRQ
QRKRBNNB
RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
NRKBNRBQ
NRKRBQNB
RBBNNQKR
QNRKBNRB
NQNRBKRB
NRKRBNQB
RBBNNQKR
RNQBBKRN
BNR...

result:

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

Test #5:

score: 0
Accepted
time: 153ms
memory: 3968kb

input:

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

output:

RBBNNQKR
RNQBBKRN
NRKBBNQR
RNNKQRBB
RKNRQBBN
RQNKRBBN
RBBNNQKR
RNQBBKRN
BNQNRKRB
NQBBRKRN
RNQKRBBN
RBBNNQKR
RNQBBKRN
NRKBBNQR
RNNKQRBB
RNNKRBBQ
RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
NRKBNRBQ
RQNKRNBB
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RNKQRBBN
RNQKRNBB
RBBNNQKR
RKNBQNBR
NRQBNKBR
RQKNRNBB
RKQNBNRB
RNNKRQBB
RBB...

result:

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

Test #6:

score: 0
Accepted
time: 176ms
memory: 3780kb

input:

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

output:

RBBNNQKR
RKNBQNBR
BBRKNRQN
QRBKNRNB
QRBKNBRN
RBBNNQKR
RNQBBKRN
NRKBBNQR
NRBQKBRN
NRBKQBRN
RBBNNQKR
RKNBQNBR
BBRKNRQN
BRKNNBRQ
BRQNNKRB
NRBKNBRQ
RBBNNQKR
RKNBQNBR
NRBQKBNR
NRKNRQBB
QRBKNNRB
RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
NRBKQNRB
RBBNNQKR
RKBNQBRN
QRNNBBKR
RNKNRQBB
RKQBNNBR
NRBKNQRB
RBBNNQKR
QNR...

result:

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

Test #7:

score: 0
Accepted
time: 149ms
memory: 3736kb

input:

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

output:

RBBNNQKR
RKBNQBRN
RKBQNRNB
RBBQKRNN
RBBNNQKR
BBRNQNKR
QNBRNBKR
RBBNKRNQ
RBBNKRQN
RBBNNQKR
BBRNQNKR
QNBRNBKR
RBBNKRNQ
RBBNNQKR
RKBNQBRN
RKBQNRNB
RBKNBRQN
RBQNKRBN
RBBNNQKR
RKNBQNBR
NRQBNKBR
RQKNRNBB
RNBBKNRQ
RBNQKRBN
RBBNNQKR
RKBNQBRN
QRNNBBKR
NBRNQKBR
NNBBQRKR
RBNNKRBQ
RBBNNQKR
RKNBQNBR
RBQKBNRN
RNB...

result:

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

Test #8:

score: 0
Accepted
time: 178ms
memory: 3972kb

input:

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

output:

RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
BRKBQNNR
QRNBKNBR
RBBNNQKR
RNQBBKRN
NRKBBNQR
NRQBKNBR
RBBNNQKR
RKNBQNBR
RKNQNRBB
NBNRQKBR
NRNBKQBR
RBBNNQKR
RKNBQNBR
NRQBNKBR
BRNBKQNR
QRNNKBBR
RBBNNQKR
RKNBQNBR
RBQKBNRN
NRNQBBKR
BRNKNBQR
NRQNKBBR
RBBNNQKR
RNQBBKRN
BRKNRNQB
BBNRKRNQ
NRNQKBBR
RBBNNQKR
RNQBBKRN
BNR...

result:

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

Test #9:

score: 0
Accepted
time: 157ms
memory: 3784kb

input:

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

output:

RBBNNQKR
RKBNQBRN
BBNNRKQR
QNBBRNKR
QBBRKNNR
RBBNNQKR
BBRNQNKR
QNBRNBKR
RQKNNBBR
NBBRKQNR
RBBNNQKR
RKBNQBRN
BBNNRKQR
RBNQKNBR
NBBRKNQR
RBBNNQKR
RKNBQNBR
RKNQNRBB
NBNRQKBR
QBNRKNBR
RBBNNQKR
RKNBQNBR
NRQBNKBR
BRKBNNQR
NBQRKNBR
RBBNNQKR
RKBNQBRN
BBQRNKNR
BQNBNRKR
NBNRKQBR
RBBNNQKR
RKNBQNBR
NRBQKBNR
BRK...

result:

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

Test #10:

score: 0
Accepted
time: 147ms
memory: 3680kb

input:

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

output:

RBBNNQKR
RKBNQBRN
BBQRNKNR
BBRQNKNR
RBBNNQKR
RKBNQBRN
QRNNBBKR
NBRNQKBR
BBRNQKNR
RBBNNQKR
BBRNQNKR
BBRNKQNR
BBRNNKQR
RBBNNQKR
RKNBQNBR
RBQKBNRN
BRNNKBQR
BQRBNKNR
RBBNNQKR
RNQBBKRN
RKNBBRNQ
QNNBRKBR
BNRBQKNR
RBBNNQKR
RKNBQNBR
RBQKBNRN
BRNNKBQR
BNRBKQNR
BNRBNKQR
RBBNNQKR
RKBNQBRN
BBNNRKQR
QBRNBKNR
RBB...

result:

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

Test #11:

score: 0
Accepted
time: 100ms
memory: 4028kb

input:

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

output:

RBBNNQKR
RKBNQBRN
BBNNRKQR
QNBBRNKR
QBBRKNNR
RQNBBNKR
RBBNNQKR
RKBNQBRN
BBNNRKQR
NRBBKQNR
RNQBBNKR
RBBNNQKR
BBRNQNKR
QNBRNBKR
RQKNNBBR
RNNBBQKR
RBBNNQKR
BBRNQNKR
RBQNBKNR
NBBNRKQR
RBQKNNBR
RQNNBBKR
RBBNNQKR
BBRNQNKR
RBQNBKNR
QBBNRKNR
RNQNBBKR
RBBNNQKR
RKBNQBRN
QRNNBBKR
BQNNRBKR
RNNQBBKR
RBBNNQKR
RKB...

result:

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

Extra Test:

score: 0
Extra Test Passed