QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#171275#7179. Fischer's Chess Guessing Gameucup-team870#AC ✓134ms8056kbC++172.2kb2023-09-09 16:43:352023-09-09 16:43:35

Judging History

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

  • [2023-09-09 16:43:35]
  • 评测
  • 测评结果:AC
  • 用时:134ms
  • 内存:8056kb
  • [2023-09-09 16:43:35]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,l,r) for(int i=l; i>=r; --i)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define vi vector<int>
#define lll __int128
const int N=1000;
const string S="KQBRN";
int d[9],ct[200],cnt,num[200];
string sta[N];
int dis[N][N];
void getv(int c,int q[]){
    int cnt=0;
    rep(i,0,7){
        if(d[i]==c)q[cnt++]=i;
    }
}
void dfs(int x){
    if(x==7){
        for(auto c:S){
            if(num[c]!=ct[c])return;
        }
        int k[2],r[2],b[2];
        getv('K',k); getv('B',b); getv('R',r);
        if(k[0]<r[0] || k[0]>r[1])return;
        if((b[0]+b[1])%2==0)return;
        ++cnt;
        sta[cnt].resize(8);
        rep(i,0,7)sta[cnt][i]=d[i];
        return;
    }
    for(auto c:S){
        ++num[c];
        d[x+1]=c; dfs(x+1);
        --num[c];
    }
}
int tot;
void wk();
int ccin(string s){
    assert(++tot<=6);
    cout<<s<<endl;
    int x;cin>>x;
    if(x==8){
        string v;cin>>v;
        if(v=="END")exit(0);
        cin>>v; wk();
    }
    return x;
}
lll cal(int i,vi &po){
    vi res(9);
    for(auto j:po)res[dis[i][j]]++;
    sort(res.begin(),res.end());
    lll ans=0;
    per(i,8,0)ans=ans*961+res[i];
    return ans;
}
void wk(){
    tot=0;
    vi po; rep(i,1,cnt)po.push_back(i);
    rep(_,1,1000){
        // assert(_<=6);
        lll ma=1e36; int ans=-1;
        rep(i,1,cnt){
            lll v=cal(i,po);
            if(v<ma)ans=i,ma=v;
        }
        int res=ccin(sta[ans]);
        vi np;
        for(auto i:po){
            if(dis[i][ans]==res)np.push_back(i);
        }
        po=np;
        assert(po.size());
        if(po.size()==1){
            ccin(sta[po[0]]);
            assert(0);
        }
    }  
}
int main(){
    ct['K']=ct['Q']=1;
    ct['B']=ct['R']=ct['N']=2;
    dfs(-1);
    assert(cnt==960);
    rep(i,1,cnt){
        rep(j,i,cnt){
            int v=0;
            rep(k,0,7)v+=sta[i][k]==sta[j][k];
            dis[i][j]=dis[j][i]=v;
        }
    }
    string s;cin>>s;
    if(s=="END")return 0;
    cin>>s;
    while(1)wk();
    return 0;
}
/*
QBBRKRNN
QBBRKRNN
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 7656kb

input:

GAME 1
4
3
3
3
8
END

output:

RQKBBNRN
RQKNBRNB
RKQNBNRB
QBRKBNNR
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 112ms
memory: 8056kb

input:

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

output:

RQKBBNRN
RQKNBRNB
RKQNBNRB
QBRKBNNR
RKRBBQNN
RQKBBNRN
RKNRBNQB
BQNRKNRB
RKRBBNQN
RQKBBNRN
RQKNBRNB
RKQNBNRB
QBRNBKNR
RKRBBNNQ
RQKBBNRN
RQKNBRNB
RKBQRNNB
QBBRKNRN
RKRBQNBN
RQKBBNRN
NRNBBKQR
RKRBBNNQ
BNRBKQRN
RKRBNQBN
RQKBBNRN
NRNBBKQR
RKRBBNNQ
QBBRKRNN
RKRBNNBQ
RQKBBNRN
NRNBBKQR
RKRBBNNQ
QBBRKNRN
RKR...

result:

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

Test #3:

score: 0
Accepted
time: 111ms
memory: 7796kb

input:

GAME 1
4
3
5
1
8
GAME 2
3
4
5
1
8
GAME 3
4
2
1
0
8
GAME 4
3
2
2
4
8
GAME 5
3
3
4
3
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
4
2
0
8
GAME 10
1
2
3
3
0
8
GAME 11
1
1
6
1
8
GAME 12
1
1
5
2
8
GAME 13
4
4
4
4
8
GAME 14
5
5
2
8
GAME 15
4
4
6
3
8
GAME 16
4
2
1
3
8
GAME 17
3
0
4
4...

output:

RQKBBNRN
RQKNBRNB
RKQNBNRB
QBBRKRNN
RKQBBNNR
RQKBBNRN
NRNBBKQR
RNNBKQBR
QBBRKRNN
RKNBBQNR
RQKBBNRN
RQKNBRNB
NRQKBBRN
QBBRKRNN
RKNBBNQR
RQKBBNRN
NRNBBKQR
RNQNBKRB
QRBBNNKR
RKQBNNBR
RQKBBNRN
NRNBBKQR
QRKBNNBR
RKBBNRQN
QBBRKRNN
RKNBQNBR
RQKBBNRN
NRKBBQNR
RQNBBKNR
RKQNBRNB
QBBRKRNN
RKNBNQBR
RQKBBNRN
NRK...

result:

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

Test #4:

score: 0
Accepted
time: 130ms
memory: 7880kb

input:

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

output:

RQKBBNRN
NRNBBKQR
RNQNBKRB
RKNQRNBB
QRKRBBNN
RQKBBNRN
NRNBBKQR
RNNBKQBR
QBBRKRNN
NRKRBBQN
RQKBBNRN
NRKBBQNR
QRKNBBRN
NRKRBBNQ
RQKBBNRN
NRNBBKQR
RNQNBKRB
QRBBNNKR
QBBRKRNN
QRKRBNNB
RQKBBNRN
NRKBBQNR
QNRBNKBR
NRKRBQNB
RQKBBNRN
NRNBBKQR
RNNBKQBR
QBBRKRNN
NRKRBNQB
RQKBBNRN
NRKBBQNR
RNQKBBNR
QRKNNBBR
QBB...

result:

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

Test #5:

score: 0
Accepted
time: 124ms
memory: 7872kb

input:

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

output:

RQKBBNRN
NRNBBKQR
RKRBBNNQ
BRKRNNQB
QBBRKRNN
RQNKRBBN
RQKBBNRN
NRKBBQNR
RKNQNRBB
BBRQNKRN
QBBRKRNN
RNQKRBBN
RQKBBNRN
NRQBBNKR
RQBNKRNB
BNNQRKRB
QBBRKRNN
RNNKRBBQ
RQKBBNRN
NRNBBKQR
RKRBBNNQ
RQKBNNBR
RQNKRNBB
RQKBBNRN
NRKBBQNR
RKNQNRBB
RBQKRNBN
QBBRKRNN
RNQKRNBB
RQKBBNRN
NRQBBNKR
RQBNKRNB
RBNKQRBN
QBB...

result:

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

Test #6:

score: 0
Accepted
time: 115ms
memory: 7764kb

input:

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

output:

RQKBBNRN
NRKBBQNR
NRBKQNRB
QBBRNKRN
QBBRKRNN
QRBKNBRN
RQKBBNRN
NRKBBQNR
RNQKBBNR
QBRNKNBR
QBBRKRNN
NRBKQBRN
RQKBBNRN
NRQBBNKR
NRQKNRBB
BRKNNQRB
QBBRKNRN
NRBKNBRQ
RQKBBNRN
NRKBBQNR
NRBKQNRB
QBBRKRNN
QRBKNNRB
RQKBBNRN
NRKBBQNR
RNQKBBNR
QRKNNBBR
QBBRKNRN
NRBKQNRB
RQKBBNRN
NRQBBNKR
NRQKNRBB
QBBRKNRN
NRB...

result:

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

Test #7:

score: 0
Accepted
time: 119ms
memory: 8028kb

input:

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

output:

RQKBBNRN
NRKBBQNR
NRBKQNRB
BBRKRQNN
QBBRKRNN
RBBQKRNN
RQKBBNRN
NRKBBQNR
RKNQNRBB
BBRQNKRN
QBBNRNKR
RBBNKRQN
RQKBBNRN
NRQBBNKR
RQBNKRNB
RNBKRNQB
RBBNKRNQ
RQKBBNRN
NRKBBQNR
RKNQNRBB
RBQKRNBN
QBBRKRNN
RBQNKRBN
RQKBBNRN
NRKBBQNR
RKNQNRBB
QBRNKRBN
RBNQKRBN
RQKBBNRN
NRQBBNKR
RQBNKRNB
BBRKNQNR
QBBRKRNN
RBN...

result:

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

Test #8:

score: 0
Accepted
time: 129ms
memory: 7884kb

input:

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

output:

RQKBBNRN
NRKBBQNR
RQNBBKNR
BQNBRNKR
QBBRKNRN
QRNBKNBR
RQKBBNRN
NRKBBQNR
RQBBKNNR
QBBRNKRN
NRQBKNBR
RQKBBNRN
NRQBBNKR
BBNRQNKR
QRBBKRNN
QBBRKNRN
NRNBKQBR
RQKBBNRN
BBRNNKQR
NRBKNBQR
BRNBKRNQ
QRNNKBBR
RQKBBNRN
BBRNNKQR
NRBKNBQR
QBBNNRKR
NRQNKBBR
RQKBBNRN
BBRNNKQR
NNBRKBQR
QBBRKRNN
NRNQKBBR
RQKBBNRN
NRQ...

result:

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

Test #9:

score: 0
Accepted
time: 127ms
memory: 7824kb

input:

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

output:

RQKBBNRN
NRQBBNKR
NRQKNRBB
BBNRKNQR
QBBRKRNN
QBBRKNNR
RQKBBNRN
BBRNNKQR
NRBKNBQR
BRNBKRNQ
NBBRKQNR
RQKBBNRN
NRQBBNKR
QBRNBNKR
QBNRBKNR
NBBRKNQR
RQKBBNRN
NRQBBNKR
NRQKNRBB
BBRNQNKR
QBBRKRNN
QBNRKNBR
RQKBBNRN
NRQBBNKR
BBNRQNKR
QBBRKNRN
NBQRKNBR
RQKBBNRN
BBRNNKQR
NRBKNBQR
BQNRNBKR
NBNRKQBR
RQKBBNRN
BBR...

result:

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

Test #10:

score: 0
Accepted
time: 126ms
memory: 7840kb

input:

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

output:

RQKBBNRN
BBRNNKQR
QBRKNRBN
QBBRKRNN
BBRQNKNR
RQKBBNRN
BBRNNKQR
QBRKNRBN
QBBRKNRN
BBRNQKNR
RQKBBNRN
BBRNNKQR
RQKBBNRN
NRKBBQNR
RQNBBKNR
QNBBRKRN
BQRBNKNR
RQKBBNRN
NRQBBNKR
NRQKNRBB
BBNRKNQR
QBBRKRNN
BNRBQKNR
RQKBBNRN
NRQBBNKR
NRQKNRBB
BBRNQNKR
QBBRKRNN
BNRBNKQR
RQKBBNRN
NRQBBNKR
NRQKNRBB
BBNRKNQR
QBB...

result:

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

Test #11:

score: 0
Accepted
time: 134ms
memory: 7828kb

input:

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

output:

RQKBBNRN
RKNRBNQB
QBBRNNKR
RQNBBNKR
RQKBBNRN
RQKNBRNB
NRQKBBRN
QBRKBNNR
RNQBBNKR
RQKBBNRN
NRNBBKQR
RNNBKQBR
RNNBBQKR
RQKBBNRN
NRNBBKQR
QRKBNNBR
RKNQBRNB
RQNNBBKR
RQKBBNRN
NRKBBQNR
RNQKBBNR
QBBRNNKR
RNQNBBKR
RQKBBNRN
NRKBBQNR
RNQKBBNR
QBBRKRNN
RNNQBBKR
RQKBBNRN
NRKBBQNR
RQNBBKNR
NBQRBNKR
BRQBNNKR
RQK...

result:

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

Extra Test:

score: 0
Extra Test Passed