QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#305291 | #7179. Fischer's Chess Guessing Game | ELDRVD | AC ✓ | 302ms | 11020kb | C++14 | 2.4kb | 2024-01-15 01:41:58 | 2024-01-15 01:41:59 |
Judging History
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