QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224337 | #7179. Fischer's Chess Guessing Game | urosk | AC ✓ | 151ms | 23056kb | C++11 | 3.8kb | 2023-10-23 01:24:09 | 2023-10-23 01:24:09 |
Judging History
answer
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
#define maxn 4000
ll tsz = 0;
map<ll,char> mp;
ll g[maxn][maxn];
string kod[maxn];
ll sad = 0;
bool test = 0;
map<string,bool> was;
map<vector<ll>,ll> calc;
vector<ll> upiti;
ll F(ll x,ll y){
string a = kod[x];
string b = kod[y];
ll ans = 0;
for(ll i = 0;i<8;i++){
if(a[i]==b[i]) ans++;
}
return ans;
}
ll val[10*maxn];
ll nxt[10*maxn][10];
ll res[10*maxn];
ll uk = 0;
ll cntok = 0;
void reshi(ll &V,vector<ll> v){
//dbg(si(v));
V = tsz++;
if(si(v)==0) return;
if(si(v)==1){
res[V] = v[0];
val[V] = v[0];
uk++;
return;
}
ll xopt = -1,maxi = 1000000;
for(ll x = 0;x<960;x++){
vector<vector<ll> > cur(9);
for(ll y : v){
cur[F(x,y)].pb(y);
}
ll curmax = 0;
for(vector<ll> s : cur) curmax = max(curmax,si(s));
if(curmax<maxi){
xopt = x;
maxi = curmax;
}
}
vector<vector<ll> > cur(9);
for(ll y : v){
cur[F(xopt,y)].pb(y);
}
val[V] = xopt;
for(ll i = 0;i<=8;i++){
reshi(nxt[V][i],cur[i]);
}
}
ll maxdub = 0;
void get(ll x,ll dub){
//dbg(x);
cout<<kod[val[x]]<<endl;
ll cnt;
if(!test) cin >> cnt;
else cnt = F(val[x],sad);
//dbg(cnt);
if(cnt==8){
cntok++;
cerr<<"ok"<<endl;
maxdub = max(dub+1,maxdub);
return;
}
get(nxt[x][cnt],dub+1);
}
ll root = 0;
void tc(){
get(root,0);
}
int main(){
fill(res,res+10*maxn,-1);
int t; t = 1;
mp[0] = mp[1] = 'B';
mp[2] = mp[3] = 'N';
mp[4] = mp[5] = 'R';
mp[6] = 'Q';
mp[7] = 'K';
vector<vector<ll> > v;
v.pb({});
for(ll i = 0;i<960;i++) v[0].pb(i);
vector<ll> p(8);
iota(all(p),0);
ll c = 0;
do{
ll b1 = -1,b2 = -1;
ll r1 = -1,r2 = -1;
ll k = -1;
string cur = "";
for(ll i = 0;i<8;i++){
if(mp[p[i]]=='B'){
if(b1==-1) b1 = i;
else b2 = i;
}else if(mp[p[i]]=='R'){
if(r1==-1) r1 = i;
else r2 = i;
}else if(mp[p[i]]=='K'){
k = i;
}
cur+=mp[p[i]];
}
c++;
if(was[cur]) continue;
was[cur] = 1;
bool ok = 1;
ok&=((k>=r1)&&(k<=r2));
ok&=((b1&1)!=(b2&1));
if(ok) kod[tsz++] = cur;
}while(next_permutation(all(p)));
dbg(c);
dbg(tsz);
for(ll i = 0;i<960;i++) for(ll j = 0;j<960;j++) g[i][j] = F(i,j);
tsz = 0;
vector<ll> vv;
for(ll i = 0;i<960;i++) vv.pb(i);
reshi(root,vv);
dbg(tsz);
dbg(uk);
for(ll ii = 0;ii<960;ii++){
//here;
//dbg(ii);
string s; if(!test) cin >> s;
else s = kod[ii];
if(s=="END") return 0;
if(!test) cin >> t;
sad = ii;
if(0){
string curs;
cin >> curs;
for(ll i = 0;i<960;i++) if(kod[i]==curs) sad = i;
}
tc();
}
dbg(cntok);
dbg(maxdub);
return (0-0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 145ms
memory: 20776kb
input:
GAME 1 1 0 2 3 1 8 END
output:
NRBBNKQR BRNNKBQR NBRKNQBR RBBKQRNN BBNNRQKR RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: 0
Accepted
time: 140ms
memory: 22640kb
input:
GAME 1 1 0 2 3 1 8 GAME 2 2 3 3 1 0 8 GAME 3 1 0 1 2 8 GAME 4 1 0 2 3 0 8 GAME 5 2 3 4 2 8 GAME 6 2 2 2 0 2 8 GAME 7 0 2 2 0 8 GAME 8 1 3 3 0 8 GAME 9 0 3 3 0 8 GAME 10 0 3 3 1 8 GAME 11 0 5 1 2 8 GAME 12 1 2 2 1 1 8 GAME 13 1 1 5 1 8 GAME 14 0 4 1 1 8 GAME 15 1 2 1 2 2 8 GAME 16 1 0 3 1 0 8 GAME 17...
output:
NRBBNKQR BRNNKBQR NBRKNQBR RBBKQRNN BBNNRQKR RKRBBQNN NRBBNKQR RNBBQKRN RQKBNNBR BBRNNQKR BBNNRKRQ RKRBBNQN NRBBNKQR BRNNKBQR NBRKNQBR BNRKQRNB RKRBBNNQ NRBBNKQR BRNNKBQR NBRKNQBR RBBKQRNN BBNNRQKR RKRBQNBN NRBBNKQR RNBBQKRN RQKBNNBR QNRBBKNR RKRBNQBN NRBBNKQR RNBBQKRN RNBQNBKR BBNRKQNR BBNRNKRQ RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 148ms
memory: 23056kb
input:
GAME 1 2 2 2 2 3 8 GAME 2 2 2 2 4 8 GAME 3 3 1 4 3 2 8 GAME 4 3 1 4 1 8 GAME 5 2 3 5 2 8 GAME 6 3 1 3 2 3 8 GAME 7 1 3 5 1 8 GAME 8 1 3 3 2 3 8 GAME 9 2 1 3 2 3 8 GAME 10 2 1 0 0 4 8 GAME 11 2 1 1 3 1 8 GAME 12 1 4 4 2 3 8 GAME 13 0 2 3 3 8 GAME 14 1 1 2 2 2 8 GAME 15 0 1 0 2 8 GAME 16 0 2 3 1 8 GAM...
output:
NRBBNKQR RNBBQKRN RNBQNBKR BBNRKQNR BBQNRKNR RKQBBNNR NRBBNKQR RNBBQKRN RNBQNBKR BBNRKQNR RKNBBQNR NRBBNKQR RBBNQKRN BRKBNNQR BNNRKBQR BBNNRQKR RKNBBNQR NRBBNKQR RBBNQKRN BRKBNNQR BNNRKBQR RKQBNNBR NRBBNKQR RNBBQKRN RQKBNNBR BBNNRQKR RKNBQNBR NRBBNKQR RBBNQKRN BRKBNNQR BBNRQKNR BBNNRQKR RKNBNQBR NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 144ms
memory: 20672kb
input:
GAME 1 1 2 1 3 0 8 GAME 2 3 1 3 1 0 8 GAME 3 2 0 3 1 0 8 GAME 4 1 1 0 0 0 8 GAME 5 2 0 4 0 1 8 GAME 6 3 0 1 2 0 8 GAME 7 2 1 1 0 8 GAME 8 2 2 1 0 8 GAME 9 3 0 0 2 8 GAME 10 2 0 4 1 0 8 GAME 11 2 1 3 1 0 8 GAME 12 3 0 0 3 8 GAME 13 2 2 0 2 8 GAME 14 3 1 6 2 8 GAME 15 2 1 1 3 3 8 GAME 16 1 3 0 4 8 GAM...
output:
NRBBNKQR BRNNKBQR BNRBKRQN BRNKRBNQ BBNNQRKR QRKRBBNN NRBBNKQR RBBNQKRN BRKBNNQR BBNRQKNR BBNNRQKR NRKRBBQN NRBBNKQR RNBBQKRN BRKQNRNB BBRQNKNR BBNNRQKR NRKRBBNQ NRBBNKQR BRNNKBQR RKQNRBBN BBRNNKRQ BBNNQRKR QRKRBNNB NRBBNKQR RNBBQKRN BRKQNRNB BBNQRNKR BBNNRQKR NRKRBQNB NRBBNKQR RBBNQKRN BNRBQNKR BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 140ms
memory: 22820kb
input:
GAME 1 0 4 3 0 8 GAME 2 0 3 0 4 8 GAME 3 0 4 4 0 8 GAME 4 0 5 1 1 8 GAME 5 0 4 3 2 8 GAME 6 0 6 4 2 8 GAME 7 1 0 2 8 GAME 8 3 4 1 3 8 GAME 9 2 2 3 1 2 8 GAME 10 0 1 1 4 8 GAME 11 1 2 3 1 2 8 GAME 12 0 2 3 6 8 GAME 13 1 0 4 2 1 8 GAME 14 0 3 1 1 8 GAME 15 1 1 2 1 3 8 GAME 16 2 2 3 0 0 8 GAME 17 1 0 1...
output:
NRBBNKQR RKNNRQBB RBNKBNRQ BNRNQKRB RQNKRBBN NRBBNKQR RKNNRQBB BQRNKRNB NRQKRNBB RNQKRBBN NRBBNKQR RKNNRQBB RBNKBNRQ BBRNKRQN RNNKRBBQ NRBBNKQR RKNNRQBB BBNRKQRN BBNRKQNR RQNKRNBB NRBBNKQR RKNNRQBB RBNKBNRQ BNRNQKRB RNQKRNBB NRBBNKQR RKNNRQBB BNNRKQRB BBNNRKRQ RNNKRQBB NRBBNKQR BRNNKBQR NBRKNQBR RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 145ms
memory: 23008kb
input:
GAME 1 3 3 1 2 0 8 GAME 2 3 4 0 1 8 GAME 3 4 3 1 0 8 GAME 4 3 2 0 4 8 GAME 5 3 3 0 2 1 8 GAME 6 4 2 0 2 8 GAME 7 1 3 1 0 8 GAME 8 2 2 1 1 0 8 GAME 9 2 1 5 1 8 GAME 10 1 2 0 2 1 8 GAME 11 2 1 5 0 8 GAME 12 2 1 6 2 8 GAME 13 3 0 2 3 2 8 GAME 14 2 1 3 5 3 8 GAME 15 4 2 4 4 8 GAME 16 4 1 4 4 8 GAME 17 4...
output:
NRBBNKQR RBBNQKRN BBQRNKNR BBNRQKRN BBNNRQKR QRBKNBRN NRBBNKQR RBBNQKRN BBNNRQKR BBNRQNKR NRBKQBRN NRBBNKQR BNRBNKRQ BNNRQBKR BNRBQKNR NRBKNBRQ NRBBNKQR RBBNQKRN BBNQRKNR BRNKNRQB QRBKNNRB NRBBNKQR RBBNQKRN BBQRNKNR BBRNKNRQ BBNNQRKR NRBKQNRB NRBBNKQR BNRBNKRQ BBNNRKQR BBNRNQKR NRBKNQRB NRBBNKQR BRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 150ms
memory: 20780kb
input:
GAME 1 1 1 2 2 1 8 GAME 2 2 3 1 1 2 8 GAME 3 1 2 2 3 1 8 GAME 4 0 3 3 3 8 GAME 5 0 3 2 1 8 GAME 6 0 4 4 4 8 GAME 7 2 4 2 0 8 GAME 8 3 3 0 1 0 8 GAME 9 2 4 3 1 8 GAME 10 1 2 2 1 0 8 GAME 11 1 1 1 8 GAME 12 2 3 1 0 1 8 GAME 13 1 2 4 3 8 GAME 14 1 1 4 1 0 8 GAME 15 1 2 4 4 8 GAME 16 0 5 2 3 8 GAME 17 0...
output:
NRBBNKQR BRNNKBQR RKQNRBBN BBRNQKRN BBNNRKQR RBBQKRNN NRBBNKQR RNBBQKRN RQKBNNBR BBNRNKRQ BBNNRQKR RBBNKRQN NRBBNKQR BRNNKBQR BNRBKRQN BBNNRKRQ BBNRNQKR RBBNKRNQ NRBBNKQR RKNNRQBB BQRNKRNB NQNRKRBB RBQNKRBN NRBBNKQR RKNNRQBB BQRNKRNB RNKRBNQB RBNQKRBN NRBBNKQR RKNNRQBB RBNKBNRQ BBRNKRQN RBNNKRBQ NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 143ms
memory: 20772kb
input:
GAME 1 3 0 3 3 8 GAME 2 4 1 2 1 1 8 GAME 3 4 1 2 2 3 8 GAME 4 2 0 1 2 3 8 GAME 5 3 1 2 2 2 8 GAME 6 3 0 1 2 2 8 GAME 7 0 0 6 2 8 GAME 8 1 4 0 4 8 GAME 9 0 1 5 4 8 GAME 10 1 2 6 2 8 GAME 11 2 3 1 1 1 8 GAME 12 1 2 6 1 8 GAME 13 0 2 0 3 8 GAME 14 0 1 6 8 GAME 15 1 4 1 1 8 GAME 16 0 2 0 1 8 GAME 17 1 1...
output:
NRBBNKQR RBBNQKRN BNRBQNKR BRKBNQNR QRNBKNBR NRBBNKQR BNRBNKRQ NQBRNBKR BBNRKRNQ BBNNRQKR NRQBKNBR NRBBNKQR BNRBNKRQ NQBRNBKR BBNRKRNQ BBNNRQKR NRNBKQBR NRBBNKQR RNBBQKRN BRKQNRNB BBRQKNNR BBNNRQKR QRNNKBBR NRBBNKQR RBBNQKRN BRKBNNQR BNNRQBKR BBNNRQKR NRQNKBBR NRBBNKQR RBBNQKRN BNRBQNKR BBNRKRQN BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 149ms
memory: 22708kb
input:
GAME 1 2 1 0 3 2 8 GAME 2 3 2 3 2 8 GAME 3 4 0 1 2 8 GAME 4 1 3 3 4 2 8 GAME 5 2 0 0 1 2 8 GAME 6 2 0 0 1 4 8 GAME 7 2 2 4 1 8 GAME 8 3 1 1 1 0 8 GAME 9 4 1 5 1 8 GAME 10 1 4 4 2 2 8 GAME 11 2 0 0 3 2 8 GAME 12 2 1 1 1 1 8 GAME 13 3 6 1 1 8 GAME 14 2 6 4 8 GAME 15 3 6 2 8 GAME 16 1 1 4 1 2 8 GAME 17...
output:
NRBBNKQR RNBBQKRN NRNKBRQB BBRKRNNQ BBNNRQKR QBBRKNNR NRBBNKQR RBBNQKRN BBNQRKNR BBNRQKRN NBBRKQNR NRBBNKQR BNRBNKRQ BRNKQBNR BBNNRQKR NBBRKNQR NRBBNKQR BRNNKBQR RBQNBNKR BBNRNQKR BBNNRKRQ QBNRKNBR NRBBNKQR RNBBQKRN BRKQNRNB BQRNNBKR BBNNRQKR NBQRKNBR NRBBNKQR RNBBQKRN BRKQNRNB BQRNNBKR BBNNRQKR NBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 151ms
memory: 22448kb
input:
GAME 1 3 2 6 3 8 GAME 2 2 2 1 5 8 GAME 3 4 4 4 4 8 GAME 4 4 5 2 8 GAME 5 3 2 4 4 8 GAME 6 5 5 2 8 GAME 7 2 1 1 4 3 8 GAME 8 3 2 5 2 8 GAME 9 4 2 5 8 GAME 10 3 3 4 2 3 8 GAME 11 4 3 1 3 8 GAME 12 3 4 3 2 8 GAME 13 3 1 2 2 1 8 GAME 14 4 3 1 5 8 GAME 15 5 3 2 1 8 GAME 16 4 5 1 8 GAME 17 5 5 3 8 GAME 18...
output:
NRBBNKQR RBBNQKRN BBNQRKNR BBNNRQKR BBRQNKNR NRBBNKQR RNBBQKRN RNBQNBKR BBRNNKRQ BBRNQKNR NRBBNKQR BNRBNKRQ BBNRNKRQ BBNNRQKR BBRNNKQR NRBBNKQR BNRBNKRQ BBNNRKRQ BQRBNKNR NRBBNKQR RBBNQKRN BBNQRKNR BRNBQKRN BNRBQKNR NRBBNKQR BQRBNNKR NRBBQNKR BNRBNKQR NRBBNKQR RNBBQKRN NRNKBRQB BBNQRKNR BBNNRQKR QBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 147ms
memory: 22580kb
input:
GAME 1 2 2 3 4 1 8 GAME 2 2 3 4 4 8 GAME 3 2 3 3 3 1 8 GAME 4 1 4 6 4 8 GAME 5 1 3 6 1 8 GAME 6 1 3 4 3 1 8 GAME 7 4 3 3 6 8 GAME 8 3 1 5 3 4 8 GAME 9 4 3 4 5 8 GAME 10 3 1 4 3 4 8 GAME 11 3 0 3 4 8 GAME 12 2 1 2 5 5 8 GAME 13 5 5 6 8 GAME 14 5 4 0 8 GAME 15 6 1 3 8 GAME 16 4 1 5 3 8 GAME 17 5 3 2 2...
output:
NRBBNKQR RNBBQKRN RNBQNBKR BBNQRNKR BBNNRKRQ RQNBBNKR NRBBNKQR RNBBQKRN RQKBNNBR QNRBBKNR RNQBBNKR NRBBNKQR RNBBQKRN RQKBNNBR BBRNNQKR BBNNRKRQ RNNBBQKR NRBBNKQR BRNNKBQR RNNQBBKR BBNNRQKR RQNNBBKR NRBBNKQR BRNNKBQR RBQNBNKR BBNNRKRQ RNQNBBKR NRBBNKQR BRNNKBQR RBQNBNKR BBNRNQKR BBNNRKRQ RNNQBBKR NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed