QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305291#7179. Fischer's Chess Guessing GameELDRVDAC ✓302ms11020kbC++142.4kb2024-01-15 01:41:582024-01-15 01:41:59

Judging History

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

  • [2024-01-15 01:41:59]
  • 评测
  • 测评结果:AC
  • 用时:302ms
  • 内存:11020kb
  • [2024-01-15 01:41:58]
  • 提交

answer

//https://qoj.ac/contest/1356/problem/7179
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define INF 1e15
#define MOD 1000000007
#define endl "\n"

#define all(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define MAXN 960
ll occ[MAXN][MAXN];
string dd[MAXN];
bool mm[MAXN];
ll Find_G(ll j)
{
    ll cnt[9];
    for(int i=0;i<9;i++) cnt[i]=0;
    for(int i=0;i<MAXN;i++)
    {
        if (mm[i]) cnt[occ[i][j]]++;
    }
    ll mx=0;
    for(int i=0;i<9;i++) mx=max(mx,cnt[i]);
    return mx;
}
bool GG(string s)
{
    ll pos[2][2],poss=-1;
    pos[0][0]=pos[0][1]=pos[1][0]=pos[1][1]=-1;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='K') poss=i;
        if(s[i]=='R') pos[0][pos[0][0]!=-1]=i;
        if(s[i]=='B') pos[1][pos[1][0]!=-1]=i;
    }
    return ((pos[1][0]&1)!=(pos[1][1]&1) && pos[0][0]<poss && poss<pos[0][1]);
}
int main()
{
    //ios::sync_with_stdio(false), cin.tie(NULL);
    string s="BBKNNQRR"; ll nxt=0;
    if(GG(s)) dd[nxt++]=s;
    while(next_permutation(all(s)))
    {
        if(GG(s)) dd[nxt++]=s;
    }
    for(int i=0;i<MAXN;i++)
    {
        for(int j=0;j<MAXN;j++)
        {
            for(int k=0;k<8;k++) occ[i][j]+=(dd[i][k]==dd[j][k]);
        }
    }
    string ss; cin>>ss;
    while(ss!="END")
    {
        ll t,cntt=0,rez,idx,mn; cin>>t;
        for(int i=0;i<MAXN;i++) mm[i]=true;
        bool check=false;
        while(cntt<6 && !check)
        {
            cntt++; mn=INF;
            for(int i=0;i<MAXN;i++)
            {
                if(Find_G(i)<mn+mm[i]) {mn = Find_G(i),idx=i;}
            }
            cout<<dd[idx]<<endl; cin>>rez;
            for(int i=0;i<MAXN;i++)
            {
                if(mm[i]) mm[i]=(occ[idx][i]==rez);
            }
            if(rez==8) check=true;
        }
        if(!check && cntt==6) return 0;
        cin>>ss;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 10800kb

input:

GAME 1
3
0
3
8
END

output:

RQKNBBRN
NRKQNBBR
BNRBQKRN
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 279ms
memory: 11016kb

input:

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

output:

RQKNBBRN
NRKQNBBR
BNRBQKRN
RKRBBQNN
RQKNBBRN
NRKQNBBR
BNRBQKRN
RKRBBQNN
RKRBBNQN
RQKNBBRN
NRKQBBNR
RBNKBRNQ
RNBKRBNQ
RKRBBNNQ
RQKNBBRN
NRKQBBNR
BNRNQKRB
RKNNRQBB
RKRBQNBN
RQKNBBRN
NRKQBBNR
BNRNQKRB
RNKBQRBN
RKRBNQBN
RQKNBBRN
NRQNBBKR
RKBQRNNB
BNRQKRNB
RKRBNNBQ
RQKNBBRN
RQBNKBNR
BRQKNBRN
RKRNQBBN
RKR...

result:

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

Test #3:

score: 0
Accepted
time: 266ms
memory: 10800kb

input:

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

output:

RQKNBBRN
NRKQBBNR
RBNNBKQR
RNNQKBBR
RKQBBNNR
RQKNBBRN
NRKQBBNR
RBNNBKQR
RNKBBRNQ
RKNBBQNR
RQKNBBRN
NRKQBBNR
RBNKBRNQ
BNNBQRKR
RKNBBNQR
RQKNBBRN
NRQNBBKR
BQRBNKNR
QBRKNNBR
RKQBNNBR
RQKNBBRN
NRQNBBKR
RNBBNKQR
BNNBRKRQ
RKNBQNBR
RQKNBBRN
NRQNBBKR
RNBBNKQR
RNNBKQBR
RKNBNQBR
RQKNBBRN
RQBNKBNR
BQNBRKNR
RKQ...

result:

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

Test #4:

score: 0
Accepted
time: 276ms
memory: 10792kb

input:

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

output:

RQKNBBRN
RQBNKBNR
RNKQRBBN
RBKRBQNN
QRKRBBNN
RQKNBBRN
RQBNKBNR
RNKBBNRQ
NRQKBBRN
NRKRBBQN
RQKNBBRN
NRKQNBBR
RQKBNNBR
NRQNBBKR
NRKRBBNQ
RQKNBBRN
NRKQBBNR
RQBNKBNR
QRKRBNNB
RQKNBBRN
NRKQBBNR
QRKBBNNR
NRKRBQNB
RQKNBBRN
NRKQBBNR
RQBNKBNR
NRNQBKRB
NRKRBNQB
RQKNBBRN
NRKQNBBR
NRKRQBBN
QRKRNBBN
RQKNBBRN
NRK...

result:

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

Test #5:

score: 0
Accepted
time: 282ms
memory: 10684kb

input:

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

output:

RQKNBBRN
RQBNKBNR
BRQKNBRN
RKQRBBNN
RQNKRBBN
RQKNBBRN
NRKQNBBR
RNNKBBQR
NNRKRBBQ
RNQKRBBN
RQKNBBRN
NRKQBBNR
BQRBKNRN
RBBNNQKR
RNNKRBBQ
RQKNBBRN
NRKQBBNR
BNRNQKRB
RNKBQRBN
RQNKRNBB
RQKNBBRN
NRQNBBKR
RNBBNKQR
QRBBKRNN
RNQKRNBB
RQKNBBRN
NRQNBBKR
RKBQRNNB
BNRQKRNB
RNNKRQBB
RQKNBBRN
NRKQBBNR
BQRBKNRN
RNK...

result:

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

Test #6:

score: 0
Accepted
time: 302ms
memory: 10684kb

input:

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

output:

RQKNBBRN
NRKQNBBR
NRNKBBRQ
QRBKNBRN
RQKNBBRN
NRKQNBBR
NRNKBBRQ
NRKBBNRQ
NRBKQBRN
RQKNBBRN
NRKQBBNR
RBNNBKQR
QRBKRBNN
NRBKNBRQ
RQKNBBRN
NRQNBBKR
RNBBNKQR
QRBBKRNN
QRBKNNRB
RQKNBBRN
NRQNBBKR
BQRBNKNR
NRKQRNBB
NRBKQNRB
RQKNBBRN
NRQNBBKR
BQRBNKNR
BBNRKRQN
NRKBRNBQ
NRBKNQRB
RQKNBBRN
RQBNKBNR
RNKBBNRQ
NRQ...

result:

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

Test #7:

score: 0
Accepted
time: 287ms
memory: 10940kb

input:

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

output:

RQKNBBRN
NRKQBBNR
RBNKBRNQ
RNBKRBNQ
RKRBBNNQ
RBBQKRNN
RQKNBBRN
NRKQNBBR
BNRBQKRN
RBQKBRNN
RBNKBNRQ
RBBNKRQN
RQKNBBRN
NRKQBBNR
BQRBKNRN
RNKRQNBB
RBBNKRNQ
RQKNBBRN
NRKQNBBR
NQNRBKRB
RNBKRBQN
RBQNKRBN
RQKNBBRN
NRKQBBNR
BQRBKNRN
BRNBQKRN
RKBBRQNN
RBNQKRBN
RQKNBBRN
NRKQBBNR
BNRNQKRB
RNKBQRBN
RQNKNRBB
RBN...

result:

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

Test #8:

score: 0
Accepted
time: 302ms
memory: 10788kb

input:

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

output:

RQKNBBRN
BBQRNNKR
QRBBNKNR
NRBBKNQR
QRNBKNBR
RQKNBBRN
BBQRNNKR
NRBBQNKR
QNBBRNKR
NRQBKNBR
RQKNBBRN
BBQRNNKR
BQRKNRNB
NRNBQKBR
NRNBKQBR
RQKNBBRN
NRKQBBNR
RBNNBKQR
RNNQKBBR
QRNNKBBR
RQKNBBRN
NRKQBBNR
RQBNKBNR
NRQNKBBR
RQKNBBRN
NRQNBBKR
NRNQKBBR
RQKNBBRN
NRQNBBKR
RKBQRNNB
BBRKRQNN
QBRKRNBN
BBRQKRNN
RQK...

result:

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

Test #9:

score: 0
Accepted
time: 287ms
memory: 11020kb

input:

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

output:

RQKNBBRN
BBQRNNKR
BNRBKQNR
QBBRKNNR
RQKNBBRN
BBQRNNKR
NRBBQNKR
NBRNKQBR
NBBRKQNR
RQKNBBRN
BBQRNNKR
BNRBKQNR
BBNRKQRN
NBBRKNQR
RQKNBBRN
BBQRNNKR
BNRBKQNR
BBNRKQRN
QBNRKNBR
RQKNBBRN
BBQRNNKR
BBNRNKQR
NBQRKNBR
RQKNBBRN
BBQRNNKR
NRBBQNKR
BBRNNKQR
NBNRKQBR
RQKNBBRN
NRQNBBKR
BQRBNKNR
RNQBKNBR
RBBQNNKR
QNB...

result:

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

Test #10:

score: 0
Accepted
time: 293ms
memory: 10728kb

input:

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

output:

RQKNBBRN
BBQRNNKR
BNRBKQNR
BRNBNQKR
BBRQNKNR
RQKNBBRN
NRQNBBKR
BQRBNKNR
QNRBBKNR
NQBBRKNR
BBRNQKNR
RQKNBBRN
NRQNBBKR
BQRBNKNR
QNRBBKNR
BRKBNQNR
BBRNNKQR
RQKNBBRN
NRQNBBKR
RNBBNKQR
RNNBKQBR
NNBBRKRQ
BQRBNKNR
RQKNBBRN
BBQRNNKR
QRBBNKNR
NRBBKNQR
BNRBQKNR
RQKNBBRN
BBQRNNKR
NRBBQNKR
BBRNNKQR
BNRBNKQR
RQK...

result:

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

Test #11:

score: 0
Accepted
time: 284ms
memory: 10752kb

input:

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

output:

RQKNBBRN
NRKQNBBR
NQNRBKRB
BQNBRKNR
RQNBBNKR
RQKNBBRN
NRKQBBNR
RBNKBRNQ
RKQBBNNR
RNQBBNKR
RQKNBBRN
NRKQBBNR
RBNKBRNQ
BNNBQRKR
RNNBBQKR
RQKNBBRN
RBNNBKQR
BBNQRKRN
RQNNBBKR
RQKNBBRN
RQBNKBNR
RNQNBBKR
RQKNBBRN
NRKQNBBR
NRNKBBRQ
NNRKBRQB
RNNQBBKR
RQKNBBRN
BBQRNNKR
BBNRKQNR
BRQBNNKR
RQKNBBRN
BBQRNNKR
BNR...

result:

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

Extra Test:

score: 0
Extra Test Passed