QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224243 | #7179. Fischer's Chess Guessing Game | urosk | TL | 30ms | 18536kb | C++14 | 3.5kb | 2023-10-23 00:47:24 | 2023-10-23 00:47:25 |
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;
if(!V) 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);
}
详细
Test #1:
score: 100
Accepted
time: 30ms
memory: 16556kb
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: 24ms
memory: 18536kb
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: 23ms
memory: 16804kb
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: 20ms
memory: 16868kb
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: 25ms
memory: 16596kb
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: 29ms
memory: 16852kb
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: 25ms
memory: 16548kb
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: 25ms
memory: 16604kb
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
Time 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...