QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224317 | #7179. Fischer's Chess Guessing Game | urosk | ML | 48ms | 22764kb | C++11 | 3.7kb | 2023-10-23 01:14:39 | 2023-10-23 01:14:39 |
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 : v){
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]);
}
}
void get(ll x){
//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;
return;
}
get(nxt[x][cnt]);
}
ll root = 0;
void tc(){
get(root);
}
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;
if(0){
string curs;
cin >> curs;
for(ll i = 0;i<960;i++) if(kod[i]==curs) sad = i;
}
tc();
}
dbg(cntok);
return (0-0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 40ms
memory: 22764kb
input:
GAME 1 1 2 2 1 8 END
output:
NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 43ms
memory: 22620kb
input:
GAME 1 1 2 2 1 8 GAME 2 2 2 3 1 1 8 GAME 3 1 2 2 0 3 8 GAME 4 1 2 1 1 8 GAME 5 2 1 0 3 5 8 GAME 6 2 2 1 0 2 8 GAME 7 0 2 3 4 3 8 GAME 8 1 2 1 0 8 GAME 9 0 3 1 6 8 GAME 10 0 3 2 3 4 8 GAME 11 0 5 2 8 GAME 12 1 1 1 3 3 8 GAME 13 1 2 2 3 4 8 GAME 14 0 4 3 4 8 GAME 15 1 2 1 0 5 8 GAME 16 1 1 3 2 2 8 GAM...
output:
NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN RKRBBQNN NRBBNKQR RBBNQNKR RNNKBBQR QBNRBKNR BNRQNBKR RKRBBNQN NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN RBKNBQNR RKRBBNNQ NRBBNKQR BNRKQBNR RNBQKRNB BBNQRNKR RKRBQNBN NRBBNKQR RBBNQNKR QRNNBKRB BBRKNRQN RQKBNRBN RKRBNQBN NRBBNKQR RBBNQNKR RNNKBBQR BRNNQKRB RQBBKRNN RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 37ms
memory: 22752kb
input:
GAME 1 2 3 3 2 3 8 GAME 2 2 2 4 8 GAME 3 3 0 5 2 8 GAME 4 3 0 2 2 6 8 GAME 5 2 4 1 2 2 8 GAME 6 3 0 3 2 8 GAME 7 1 3 0 8 GAME 8 1 3 0 6 4 8 GAME 9 2 3 1 8 GAME 10 2 3 1 5 8 GAME 11 2 2 4 4 8 GAME 12 1 3 0 5 5 8 GAME 13 0 2 3 8 GAME 14 1 0 1 3 8 GAME 15 0 1 2 4 1 8 GAME 16 0 2 2 2 8 GAME 17 1 0 3 6 8...
output:
NRBBNKQR RBBNQNKR RQBBKNRN RKBNNQRB RNBQKBNR RKQBBNNR NRBBNKQR RBBNQNKR RNNKBBQR RKNBBQNR NRBBNKQR NRBQKBRN RBNNBKQR RBQNNKBR RKNBBNQR NRBBNKQR NRBQKBRN RBNNBKQR BNRBQKNR RQKBNNBR RKQBNNBR NRBBNKQR RBBNQNKR BBRNNQKR RNBNQKRB RBBKRNQN RKNBQNBR NRBBNKQR NRBQKBRN RBNNBKQR BBQRNKNR RKNBNQBR NRBBNKQR BNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 48ms
memory: 20760kb
input:
GAME 1 1 2 1 0 3 8 GAME 2 3 4 3 3 8 GAME 3 2 0 8 GAME 4 1 1 0 2 8 GAME 5 2 0 6 4 8 GAME 6 3 2 3 1 2 8 GAME 7 2 0 4 4 8 GAME 8 2 1 1 4 8 GAME 9 3 3 0 2 8 GAME 10 2 1 3 2 3 8 GAME 11 2 2 0 6 8 GAME 12 3 2 3 2 8 GAME 13 2 0 3 2 8 GAME 14 3 2 5 8 GAME 15 2 1 1 5 8 GAME 16 1 3 1 1 8 GAME 17 2 1 2 2 8 GAM...
output:
NRBBNKQR BNRKQBNR RNBQKRNB BBNQRNKR RKRNBBQN QRKRBBNN NRBBNKQR NRBQKBRN NBBRQKRN NRNQBKRB NRKRBBQN NRBBNKQR RBBNQNKR NRKRBBNQ NRBBNKQR BNRKQBNR RBQKNRBN BRNNKQRB QRKRBNNB NRBBNKQR RBBNQNKR NRKRBBNQ BRKRNBNQ NRKRBQNB NRBBNKQR NRBQKBRN BRKBNNRQ BRNBKQNR NNRBBKRQ NRKRBNQB NRBBNKQR RBBNQNKR NRKRBBNQ BRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 40ms
memory: 20780kb
input:
GAME 1 0 4 3 8 GAME 2 0 3 6 4 8 GAME 3 0 4 4 8 GAME 4 0 5 8 GAME 5 0 4 2 4 8 GAME 6 0 6 4 8 GAME 7 1 3 1 3 8 GAME 8 3 2 1 2 2 8 GAME 9 2 3 2 1 8 GAME 10 0 1 0 8 GAME 11 1 1 5 8 GAME 12 0 2 3 4 8 GAME 13 1 1 8 GAME 14 0 3 5 8 GAME 15 1 1 6 8 GAME 16 2 2 2 3 1 8 GAME 17 1 4 2 1 8 GAME 18 3 1 1 2 8 GAM...
output:
NRBBNKQR RKNNRQBB RBNNKRBQ RQNKRBBN NRBBNKQR RKNNRQBB RBQKRNBN RBKQRNBN RNQKRBBN NRBBNKQR RKNNRQBB RBNNKRBQ RNNKRBBQ NRBBNKQR RKNNRQBB RQNKRNBB NRBBNKQR RKNNRQBB RBNNKRBQ RNNKBQRB RNQKRNBB NRBBNKQR RKNNRQBB RKNNRBBQ RNNKRQBB NRBBNKQR BNRKQBNR BQRKNNRB BBNNQRKR RBBKQRNN NRBBNKQR NRBQKBRN BRKBNNRQ RNB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 33ms
memory: 20764kb
input:
GAME 1 3 5 2 8 GAME 2 3 6 4 8 GAME 3 4 1 3 8 GAME 4 3 3 2 3 4 8 GAME 5 3 4 4 4 8 GAME 6 4 1 4 8 GAME 7 1 2 0 3 8 GAME 8 2 0 4 1 4 8 GAME 9 2 0 5 8 GAME 10 1 1 1 2 4 8 GAME 11 2 1 4 3 8 GAME 12 2 0 3 4 2 8 GAME 13 3 2 3 4 8 GAME 14 2 2 4 3 8 GAME 15 4 4 8 GAME 16 4 3 2 2 8 GAME 17 4 4 4 2 8 GAME 18 6...
output:
NRBBNKQR NRBQKBRN NRBQKRNB QRBKNBRN NRBBNKQR NRBQKBRN NRBQKNRB NRBKQBRN NRBBNKQR BRNBQKNR NBBRNQKR NRBKNBRQ NRBBNKQR NRBQKBRN RNBBQKRN NRQNBKRB NRBKQRNB QRBKNNRB NRBBNKQR NRBQKBRN NBBRQKRN NNBQRKRB NRBKQNRB NRBBNKQR BRNBQKNR NBBRNQKR NRBKNQRB NRBBNKQR BNRKQBNR RNBQKRNB NBRKBNRQ QRNKBBRN NRBBNKQR RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 36ms
memory: 20760kb
input:
GAME 1 1 1 4 5 8 GAME 2 2 4 2 3 8 GAME 3 1 1 3 5 8 GAME 4 0 3 5 5 8 GAME 5 0 3 4 4 8 GAME 6 0 4 8 GAME 7 2 2 1 0 8 GAME 8 3 3 5 3 8 GAME 9 2 2 2 1 8 GAME 10 1 1 2 1 8 GAME 11 1 2 8 GAME 12 2 3 3 4 8 GAME 13 1 0 4 8 GAME 14 1 1 5 3 8 GAME 15 1 1 3 4 4 8 GAME 16 0 5 5 8 GAME 17 0 4 5 2 8 GAME 18 0 4 5...
output:
NRBBNKQR BNRKQBNR RBQKNRBN NBRQKRBN RBBQKRNN NRBBNKQR RBBNQNKR BBRNNQKR RBNKBNQR RBBNKRQN NRBBNKQR BNRKQBNR RBQKNRBN NBRNKRBQ RBBNKRNQ NRBBNKQR RKNNRQBB RBQKRNBN RBNKQRBN RBQNKRBN NRBBNKQR RKNNRQBB RBQKRNBN RBNKBQRN RBNQKRBN NRBBNKQR RKNNRQBB RBNNKRBQ NRBBNKQR RBBNQNKR RNNKBBQR BRNNQKRB RQBBKRNN NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 41ms
memory: 20776kb
input:
GAME 1 3 2 3 5 8 GAME 2 4 3 4 8 GAME 3 4 4 3 6 8 GAME 4 2 2 3 3 3 8 GAME 5 3 4 1 4 8 GAME 6 3 5 4 8 GAME 7 0 0 6 8 GAME 8 1 2 2 3 2 8 GAME 9 0 1 3 5 8 GAME 10 1 3 3 3 4 8 GAME 11 2 0 0 8 GAME 12 1 4 3 8 GAME 13 0 2 1 2 8 GAME 14 0 1 3 8 GAME 15 1 3 3 3 8 GAME 16 0 2 1 3 8 GAME 17 1 1 4 8 GAME 18 1 1...
output:
NRBBNKQR NRBQKBRN BRKBNNRQ BRNBKQNR QRNBKNBR NRBBNKQR BRNBQKNR RNQBNKBR NRQBKNBR NRBBNKQR BRNBQKNR BRNKNBQR NRNBBQKR NRNBKQBR NRBBNKQR RBBNQNKR RNNKBBQR QBNRBKNR BQNRNBKR QRNNKBBR NRBBNKQR NRBQKBRN NBBRQKRN NRNQBBKR NRQNKBBR NRBBNKQR NRBQKBRN NRBQKRNB NRNQKBBR NRBBNKQR RKNNRQBB BBQRKRNN BBRQKRNN NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: -100
Memory Limit Exceeded
input:
GAME 1 2 4 2 3 3 8 GAME 2 3 3 1 4 8 GAME 3 4 1 5 4 8 GAME 4 1 1 2 0 8 GAME 5 2 3 2 5 8 GAME 6 2 2 2 3 2 8 GAME 7 2 2 3 4 2 8 GAME 8 3 4 3 1 8 GAME 9 4 1 4 2 8 GAME 10 1 3 0 2 8 GAME 11 2 1 1 0 4 8 GAME 12 2 1 0 0 8 GAME 13 3 4 5 3 8 GAME 14 2 5 8 GAME 15 3 2 3 0 8 GAME 16 1 0 1 4 8 GAME 17 1 0 3 2 8...
output:
NRBBNKQR RBBNQNKR BBRNNQKR RBNKBNQR RBBNKRQN QBBRKNNR NRBBNKQR NRBQKBRN RNBBQKRN NBBQRNKR NBBRKQNR NRBBNKQR BRNBQKNR NBBRNQKR NBBRNKRQ NBBRKNQR NRBBNKQR BNRKQBNR RBQKNRBN RNKBBQRN QBNRKNBR NRBBNKQR RBBNQNKR RQBBKNRN BBNRKNQR NBQRKNBR NRBBNKQR RBBNQNKR RNNKBBQR BBRKNQNR BRQNKBNR NBNRKQBR NRBBNKQR RBB...