QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224246#7179. Fischer's Chess Guessing GameuroskTL 33ms18828kbC++143.5kb2023-10-23 00:48:182023-10-23 00:48:18

Judging History

你现在查看的是最新测评结果

  • [2023-10-23 00:48:18]
  • 评测
  • 测评结果:TL
  • 用时:33ms
  • 内存:18828kb
  • [2023-10-23 00:48:18]
  • 提交

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: 18ms
memory: 17052kb

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: 26ms
memory: 18592kb

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: 25ms
memory: 18720kb

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: 32ms
memory: 18552kb

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: 23ms
memory: 18752kb

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: 32ms
memory: 16788kb

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: 33ms
memory: 18828kb

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: 29ms
memory: 16444kb

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...

result: