QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#171275 | #7179. Fischer's Chess Guessing Game | ucup-team870# | AC ✓ | 134ms | 8056kb | C++17 | 2.2kb | 2023-09-09 16:43:35 | 2023-09-09 16:43:35 |
Judging History
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