QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224269 | #7179. Fischer's Chess Guessing Game | urosk | TL | 33ms | 18572kb | C++14 | 3.5kb | 2023-10-23 00:54:22 | 2023-10-23 00:54:23 |
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 3000
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++) ans+=(a[i]==b[i]);
return ans;
}
ll val[10*maxn];
ll nxt[10*maxn][10];
ll res[10*maxn];
void reshi(ll &V,vector<ll> v){
//dbg(si(v));
if(si(v)==0) return;
V = tsz++;
if(si(v)==1){
res[V] = v[0];
val[V] = v[0];
return;
}
ll xopt = -1,maxi = 1000000;
for(ll x : v){
vector<vector<ll> > cur(9);
for(ll y : v){
cur[g[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) return;
if(nxt[x][cnt]==0){
while(1) here;
}
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);
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]];
}
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(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);
while(1){
//here;
string s; cin >> s;
if(s=="END") return 0;
cin >> t;
if(test){
string curs;
cin >> curs;
for(ll i = 0;i<960;i++) if(kod[i]==curs) sad = i;
}
tc();
}
return (0-0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 30ms
memory: 16544kb
input:
GAME 1 3 1 6 8 END
output:
RQKNBBRN NRBKQBRN RKQBBRNN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 4 (1 test case)
Test #2:
score: 0
Accepted
time: 33ms
memory: 18572kb
input:
GAME 1 3 1 6 8 GAME 2 3 1 5 8 GAME 3 2 2 4 4 8 GAME 4 2 3 0 4 8 GAME 5 2 4 4 8 GAME 6 1 1 2 5 8 GAME 7 4 3 6 8 GAME 8 5 5 3 8 GAME 9 4 4 5 8 GAME 10 2 3 1 2 8 GAME 11 3 0 1 8 GAME 12 3 0 2 3 8 GAME 13 3 2 3 1 6 8 GAME 14 4 3 4 8 GAME 15 3 1 2 8 GAME 16 1 3 2 0 8 GAME 17 2 3 0 6 4 8 GAME 18 2 4 6 8 G...
output:
RQKNBBRN NRBKQBRN RKQBBRNN RKRBBQNN RQKNBBRN NRBKQBRN RKQBBRNN RKRBBNQN RQKNBBRN RKNQNBBR RQBBKNNR RNQBBNKR RKRBBNNQ RQKNBBRN RKNQNBBR NRNKBBQR RKQNRNBB RKRBQNBN RQKNBBRN RKNQNBBR RKQNNRBB RKRBNQBN RQKNBBRN RNBQKRNB NNRBBKQR RKNBQNBR RKRBNNBQ RQKNBBRN RQBNKBNR RKQRBBNN RKRQBBNN RQKNBBRN RKNQBBRN RBK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 30ms
memory: 18544kb
input:
GAME 1 2 3 2 4 8 GAME 2 2 4 2 6 8 GAME 3 2 4 2 8 GAME 4 1 1 2 6 8 GAME 5 1 1 2 8 GAME 6 1 1 2 6 6 8 GAME 7 4 5 8 GAME 8 3 1 4 6 8 GAME 9 4 4 4 2 8 GAME 10 3 1 3 1 8 GAME 11 2 8 GAME 12 3 2 4 8 GAME 13 4 2 3 8 GAME 14 4 1 3 4 8 GAME 15 3 0 3 5 8 GAME 16 3 2 2 3 5 8 GAME 17 3 1 2 3 3 8 GAME 18 2 3 0 3...
output:
RQKNBBRN RKNQNBBR NRNKBBQR RKNRBQNB RKQBBNNR RQKNBBRN RKNQNBBR RKQNNRBB RKNBBNQR RKNBBQNR RQKNBBRN RKNQNBBR RKQNNRBB RKNBBNQR RQKNBBRN RNBQKRNB NNRBBKQR RKNBQNBR RKQBNNBR RQKNBBRN RNBQKRNB NNRBBKQR RKNBQNBR RQKNBBRN RNBQKRNB NNRBBKQR RKNBQNBR RKQBNNBR RKNBNQBR RQKNBBRN RQBNKBNR RKQNBBNR RQKNBBRN NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 23ms
memory: 17008kb
input:
GAME 1 4 2 3 5 8 GAME 2 4 1 2 2 8 GAME 3 3 3 6 8 GAME 4 2 0 1 1 8 GAME 5 2 0 0 4 8 GAME 6 2 0 0 3 8 GAME 7 3 3 3 2 8 GAME 8 3 5 3 8 GAME 9 2 3 3 8 GAME 10 1 1 0 8 GAME 11 1 1 1 3 8 GAME 12 1 1 1 2 0 8 GAME 13 2 0 3 1 8 GAME 14 2 0 3 2 0 8 GAME 15 1 1 1 8 GAME 16 3 3 5 5 8 GAME 17 4 2 4 2 8 GAME 18 3...
output:
RQKNBBRN RQBNKBNR RNKQRBBN RBKRBQNN QRKRBBNN RQKNBBRN RQBNKBNR QBRNBKRN RNKQBNRB NRKRBBQN RQKNBBRN NRBKQBRN NRKQBBNR NRKRBBNQ RQKNBBRN RKNQNBBR QNBBRKRN NBRKBRQN QRKRBNNB RQKNBBRN RKNQNBBR QNBBRKRN NQRKBRNB NRKRBQNB RQKNBBRN RKNQNBBR QNBBRKRN NQRKBRNB NRKRBNQB RQKNBBRN NRBKQBRN NRKQBBNR RQBKNBNR QRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 30ms
memory: 16800kb
input:
GAME 1 4 3 3 4 8 GAME 2 3 3 1 4 8 GAME 3 2 4 2 2 3 8 GAME 4 2 3 2 3 8 GAME 5 1 3 3 8 GAME 6 1 3 2 1 8 GAME 7 2 1 0 4 3 8 GAME 8 2 2 2 1 1 8 GAME 9 1 4 1 3 8 GAME 10 3 2 0 4 8 GAME 11 3 2 0 3 8 GAME 12 2 2 2 0 8 GAME 13 2 3 1 2 1 8 GAME 14 2 3 2 2 8 GAME 15 1 2 1 2 8 GAME 16 2 2 4 1 2 8 GAME 17 1 6 5...
output:
RQKNBBRN RQBNKBNR RKQRBBNN BQNRKBRN RQNKRBBN RQKNBBRN NRBKQBRN NRKQBBNR RKNRQBBN RNQKRBBN RQKNBBRN RKNQNBBR RKQNNRBB RKNBBNQR QRNNKBBR RNNKRBBQ RQKNBBRN RKNQNBBR NRNKBBQR RKNRBQNB RQNKRNBB RQKNBBRN RNBQKRNB RNBBQNKR RNQKRNBB RQKNBBRN RNBQKRNB RNBBQNKR BNQRKBNR RNNKRQBB RQKNBBRN RKNQNBBR BRKBNNRQ RNQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 33ms
memory: 17092kb
input:
GAME 1 3 6 5 8 GAME 2 3 8 GAME 3 2 2 1 8 GAME 4 1 2 1 8 GAME 5 1 2 2 8 GAME 6 1 2 1 6 8 GAME 7 4 1 4 3 8 GAME 8 4 1 3 4 2 8 GAME 9 3 5 8 GAME 10 2 1 3 4 8 GAME 11 2 0 1 3 3 8 GAME 12 2 1 2 3 8 GAME 13 1 1 1 3 1 8 GAME 14 1 1 1 3 2 8 GAME 15 1 0 2 3 5 8 GAME 16 1 2 4 3 8 GAME 17 1 2 5 2 8 GAME 18 1 1...
output:
RQKNBBRN NRBKQBRN NRBQKBRN QRBKNBRN RQKNBBRN NRBKQBRN RQKNBBRN RKNQNBBR RQBBKNNR NRBKNBRQ RQKNBBRN RNBQKRNB BNRKQBNR QRBKNNRB RQKNBBRN RNBQKRNB BNRKQBNR NRBKQNRB RQKNBBRN RNBQKRNB BNRKQBNR QRBKNNRB NRBKNQRB RQKNBBRN RQBNKBNR QBRNBKRN RNQBBKRN QRNKBBRN RQKNBBRN RQBNKBNR QBRNBKRN RKQBBNRN RBKRBNQN NRQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 29ms
memory: 16784kb
input:
GAME 1 2 2 4 1 3 8 GAME 2 3 2 1 1 8 GAME 3 2 1 1 4 3 8 GAME 4 3 1 4 1 8 GAME 5 2 4 3 2 1 8 GAME 6 2 3 1 1 8 GAME 7 3 2 0 1 8 GAME 8 2 1 1 8 GAME 9 1 6 4 4 8 GAME 10 3 1 3 4 8 GAME 11 1 8 GAME 12 2 1 0 4 8 GAME 13 3 1 4 2 8 GAME 14 2 2 3 4 8 GAME 15 1 4 2 4 8 GAME 16 3 0 3 2 8 GAME 17 2 2 2 2 8 GAME ...
output:
RQKNBBRN RKNQNBBR RQBBKNNR RNQBBNKR QRBNKBNR RBBQKRNN RQKNBBRN NRBKQBRN QRKNNBBR QNRBBKRN RBBNKRQN RQKNBBRN RKNQNBBR BRKBNNRQ RNBBKRQN RBBKRNQN RBBNKRNQ RQKNBBRN NRBKQBRN RKQBBRNN RKNRBBNQ RBQNKRBN RQKNBBRN RKNQNBBR RKQNNRBB RNKBNQBR RKBRNBNQ RBNQKRBN RQKNBBRN RKNQNBBR NRNKBBQR RQBBNNKR RBNNKRBQ RQK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: -100
Time Limit Exceeded
input:
GAME 1 0 2 4 5 8 GAME 2 0 3 5 3 8 GAME 3 0 1 1 8 GAME 4 2 4 2 2 8 GAME 5 2 3 4 2 8 GAME 6 1 2 2 2 8 GAME 7 1 4 1 2 8 GAME 8 2 0 1 5 2 8 GAME 9 1 3 0 2 5 8 GAME 10 2 0 2 4 8 GAME 11 1 3 2 3 8 GAME 12 0 1 1 2 8 GAME 13 2 0 0 5 8 GAME 14 0 1 2 4 1 8 GAME 15 1 4 3 2 1 8 GAME 16 2 1 0 1 3 8 GAME 17 1 3 0...
output:
RQKNBBRN BBQRNNKR QRBBNKNR NRBBKNQR QRNBKNBR RQKNBBRN BBQRNNKR NRBBQNKR QNBBRNKR NRQBKNBR RQKNBBRN BBQRNNKR QRBKRNNB NRNBKQBR RQKNBBRN RKNQNBBR RKQNNRBB RKNBBNQR QRNNKBBR RQKNBBRN RKNQNBBR NRNKBBQR QNNRBBKR NRQNKBBR RQKNBBRN RNBQKRNB BNRKQBNR NRBKQNRB NRNQKBBR RQKNBBRN RNBQKRNB QNBRKNRB RKNQNRBB BBR...