QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224269#7179. Fischer's Chess Guessing GameuroskTL 33ms18572kbC++143.5kb2023-10-23 00:54:222023-10-23 00:54:23

Judging History

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

  • [2023-10-23 00:54:23]
  • 评测
  • 测评结果:TL
  • 用时:33ms
  • 内存:18572kb
  • [2023-10-23 00:54:22]
  • 提交

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

result: