QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224337#7179. Fischer's Chess Guessing GameuroskAC ✓151ms23056kbC++113.8kb2023-10-23 01:24:092023-10-23 01:24:09

Judging History

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

  • [2023-10-23 01:24:09]
  • 评测
  • 测评结果:AC
  • 用时:151ms
  • 内存:23056kb
  • [2023-10-23 01:24:09]
  • 提交

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 = 0;x<960;x++){
        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]);
    }
}
ll maxdub = 0;
void get(ll x,ll dub){
    //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;
        maxdub = max(dub+1,maxdub);
        return;
    }
    get(nxt[x][cnt],dub+1);
}
ll root = 0;
void tc(){
    get(root,0);
}
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;
        sad = ii;
        if(0){
            string curs;
            cin >> curs;
            for(ll i = 0;i<960;i++) if(kod[i]==curs) sad = i;
        }
		tc();
	}
	dbg(cntok);
	dbg(maxdub);
	return (0-0);
}

详细

Test #1:

score: 100
Accepted
time: 145ms
memory: 20776kb

input:

GAME 1
1
0
2
3
1
8
END

output:

NRBBNKQR
BRNNKBQR
NBRKNQBR
RBBKQRNN
BBNNRQKR
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 6 (1 test case)

Test #2:

score: 0
Accepted
time: 140ms
memory: 22640kb

input:

GAME 1
1
0
2
3
1
8
GAME 2
2
3
3
1
0
8
GAME 3
1
0
1
2
8
GAME 4
1
0
2
3
0
8
GAME 5
2
3
4
2
8
GAME 6
2
2
2
0
2
8
GAME 7
0
2
2
0
8
GAME 8
1
3
3
0
8
GAME 9
0
3
3
0
8
GAME 10
0
3
3
1
8
GAME 11
0
5
1
2
8
GAME 12
1
2
2
1
1
8
GAME 13
1
1
5
1
8
GAME 14
0
4
1
1
8
GAME 15
1
2
1
2
2
8
GAME 16
1
0
3
1
0
8
GAME 17...

output:

NRBBNKQR
BRNNKBQR
NBRKNQBR
RBBKQRNN
BBNNRQKR
RKRBBQNN
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBRNNQKR
BBNNRKRQ
RKRBBNQN
NRBBNKQR
BRNNKBQR
NBRKNQBR
BNRKQRNB
RKRBBNNQ
NRBBNKQR
BRNNKBQR
NBRKNQBR
RBBKQRNN
BBNNRQKR
RKRBQNBN
NRBBNKQR
RNBBQKRN
RQKBNNBR
QNRBBKNR
RKRBNQBN
NRBBNKQR
RNBBQKRN
RNBQNBKR
BBNRKQNR
BBNRNKRQ
RKR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #3:

score: 0
Accepted
time: 148ms
memory: 23056kb

input:

GAME 1
2
2
2
2
3
8
GAME 2
2
2
2
4
8
GAME 3
3
1
4
3
2
8
GAME 4
3
1
4
1
8
GAME 5
2
3
5
2
8
GAME 6
3
1
3
2
3
8
GAME 7
1
3
5
1
8
GAME 8
1
3
3
2
3
8
GAME 9
2
1
3
2
3
8
GAME 10
2
1
0
0
4
8
GAME 11
2
1
1
3
1
8
GAME 12
1
4
4
2
3
8
GAME 13
0
2
3
3
8
GAME 14
1
1
2
2
2
8
GAME 15
0
1
0
2
8
GAME 16
0
2
3
1
8
GAM...

output:

NRBBNKQR
RNBBQKRN
RNBQNBKR
BBNRKQNR
BBQNRKNR
RKQBBNNR
NRBBNKQR
RNBBQKRN
RNBQNBKR
BBNRKQNR
RKNBBQNR
NRBBNKQR
RBBNQKRN
BRKBNNQR
BNNRKBQR
BBNNRQKR
RKNBBNQR
NRBBNKQR
RBBNQKRN
BRKBNNQR
BNNRKBQR
RKQBNNBR
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBNNRQKR
RKNBQNBR
NRBBNKQR
RBBNQKRN
BRKBNNQR
BBNRQKNR
BBNNRQKR
RKNBNQBR
NRB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #4:

score: 0
Accepted
time: 144ms
memory: 20672kb

input:

GAME 1
1
2
1
3
0
8
GAME 2
3
1
3
1
0
8
GAME 3
2
0
3
1
0
8
GAME 4
1
1
0
0
0
8
GAME 5
2
0
4
0
1
8
GAME 6
3
0
1
2
0
8
GAME 7
2
1
1
0
8
GAME 8
2
2
1
0
8
GAME 9
3
0
0
2
8
GAME 10
2
0
4
1
0
8
GAME 11
2
1
3
1
0
8
GAME 12
3
0
0
3
8
GAME 13
2
2
0
2
8
GAME 14
3
1
6
2
8
GAME 15
2
1
1
3
3
8
GAME 16
1
3
0
4
8
GAM...

output:

NRBBNKQR
BRNNKBQR
BNRBKRQN
BRNKRBNQ
BBNNQRKR
QRKRBBNN
NRBBNKQR
RBBNQKRN
BRKBNNQR
BBNRQKNR
BBNNRQKR
NRKRBBQN
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBRQNKNR
BBNNRQKR
NRKRBBNQ
NRBBNKQR
BRNNKBQR
RKQNRBBN
BBRNNKRQ
BBNNQRKR
QRKRBNNB
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBNQRNKR
BBNNRQKR
NRKRBQNB
NRBBNKQR
RBBNQKRN
BNRBQNKR
BBN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #5:

score: 0
Accepted
time: 140ms
memory: 22820kb

input:

GAME 1
0
4
3
0
8
GAME 2
0
3
0
4
8
GAME 3
0
4
4
0
8
GAME 4
0
5
1
1
8
GAME 5
0
4
3
2
8
GAME 6
0
6
4
2
8
GAME 7
1
0
2
8
GAME 8
3
4
1
3
8
GAME 9
2
2
3
1
2
8
GAME 10
0
1
1
4
8
GAME 11
1
2
3
1
2
8
GAME 12
0
2
3
6
8
GAME 13
1
0
4
2
1
8
GAME 14
0
3
1
1
8
GAME 15
1
1
2
1
3
8
GAME 16
2
2
3
0
0
8
GAME 17
1
0
1...

output:

NRBBNKQR
RKNNRQBB
RBNKBNRQ
BNRNQKRB
RQNKRBBN
NRBBNKQR
RKNNRQBB
BQRNKRNB
NRQKRNBB
RNQKRBBN
NRBBNKQR
RKNNRQBB
RBNKBNRQ
BBRNKRQN
RNNKRBBQ
NRBBNKQR
RKNNRQBB
BBNRKQRN
BBNRKQNR
RQNKRNBB
NRBBNKQR
RKNNRQBB
RBNKBNRQ
BNRNQKRB
RNQKRNBB
NRBBNKQR
RKNNRQBB
BNNRKQRB
BBNNRKRQ
RNNKRQBB
NRBBNKQR
BRNNKBQR
NBRKNQBR
RBB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #6:

score: 0
Accepted
time: 145ms
memory: 23008kb

input:

GAME 1
3
3
1
2
0
8
GAME 2
3
4
0
1
8
GAME 3
4
3
1
0
8
GAME 4
3
2
0
4
8
GAME 5
3
3
0
2
1
8
GAME 6
4
2
0
2
8
GAME 7
1
3
1
0
8
GAME 8
2
2
1
1
0
8
GAME 9
2
1
5
1
8
GAME 10
1
2
0
2
1
8
GAME 11
2
1
5
0
8
GAME 12
2
1
6
2
8
GAME 13
3
0
2
3
2
8
GAME 14
2
1
3
5
3
8
GAME 15
4
2
4
4
8
GAME 16
4
1
4
4
8
GAME 17
4...

output:

NRBBNKQR
RBBNQKRN
BBQRNKNR
BBNRQKRN
BBNNRQKR
QRBKNBRN
NRBBNKQR
RBBNQKRN
BBNNRQKR
BBNRQNKR
NRBKQBRN
NRBBNKQR
BNRBNKRQ
BNNRQBKR
BNRBQKNR
NRBKNBRQ
NRBBNKQR
RBBNQKRN
BBNQRKNR
BRNKNRQB
QRBKNNRB
NRBBNKQR
RBBNQKRN
BBQRNKNR
BBRNKNRQ
BBNNQRKR
NRBKQNRB
NRBBNKQR
BNRBNKRQ
BBNNRKQR
BBNRNQKR
NRBKNQRB
NRBBNKQR
BRN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #7:

score: 0
Accepted
time: 150ms
memory: 20780kb

input:

GAME 1
1
1
2
2
1
8
GAME 2
2
3
1
1
2
8
GAME 3
1
2
2
3
1
8
GAME 4
0
3
3
3
8
GAME 5
0
3
2
1
8
GAME 6
0
4
4
4
8
GAME 7
2
4
2
0
8
GAME 8
3
3
0
1
0
8
GAME 9
2
4
3
1
8
GAME 10
1
2
2
1
0
8
GAME 11
1
1
1
8
GAME 12
2
3
1
0
1
8
GAME 13
1
2
4
3
8
GAME 14
1
1
4
1
0
8
GAME 15
1
2
4
4
8
GAME 16
0
5
2
3
8
GAME 17
0...

output:

NRBBNKQR
BRNNKBQR
RKQNRBBN
BBRNQKRN
BBNNRKQR
RBBQKRNN
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBNRNKRQ
BBNNRQKR
RBBNKRQN
NRBBNKQR
BRNNKBQR
BNRBKRQN
BBNNRKRQ
BBNRNQKR
RBBNKRNQ
NRBBNKQR
RKNNRQBB
BQRNKRNB
NQNRKRBB
RBQNKRBN
NRBBNKQR
RKNNRQBB
BQRNKRNB
RNKRBNQB
RBNQKRBN
NRBBNKQR
RKNNRQBB
RBNKBNRQ
BBRNKRQN
RBNNKRBQ
NRB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #8:

score: 0
Accepted
time: 143ms
memory: 20772kb

input:

GAME 1
3
0
3
3
8
GAME 2
4
1
2
1
1
8
GAME 3
4
1
2
2
3
8
GAME 4
2
0
1
2
3
8
GAME 5
3
1
2
2
2
8
GAME 6
3
0
1
2
2
8
GAME 7
0
0
6
2
8
GAME 8
1
4
0
4
8
GAME 9
0
1
5
4
8
GAME 10
1
2
6
2
8
GAME 11
2
3
1
1
1
8
GAME 12
1
2
6
1
8
GAME 13
0
2
0
3
8
GAME 14
0
1
6
8
GAME 15
1
4
1
1
8
GAME 16
0
2
0
1
8
GAME 17
1
1...

output:

NRBBNKQR
RBBNQKRN
BNRBQNKR
BRKBNQNR
QRNBKNBR
NRBBNKQR
BNRBNKRQ
NQBRNBKR
BBNRKRNQ
BBNNRQKR
NRQBKNBR
NRBBNKQR
BNRBNKRQ
NQBRNBKR
BBNRKRNQ
BBNNRQKR
NRNBKQBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBRQKNNR
BBNNRQKR
QRNNKBBR
NRBBNKQR
RBBNQKRN
BRKBNNQR
BNNRQBKR
BBNNRQKR
NRQNKBBR
NRBBNKQR
RBBNQKRN
BNRBQNKR
BBNRKRQN
BBN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #9:

score: 0
Accepted
time: 149ms
memory: 22708kb

input:

GAME 1
2
1
0
3
2
8
GAME 2
3
2
3
2
8
GAME 3
4
0
1
2
8
GAME 4
1
3
3
4
2
8
GAME 5
2
0
0
1
2
8
GAME 6
2
0
0
1
4
8
GAME 7
2
2
4
1
8
GAME 8
3
1
1
1
0
8
GAME 9
4
1
5
1
8
GAME 10
1
4
4
2
2
8
GAME 11
2
0
0
3
2
8
GAME 12
2
1
1
1
1
8
GAME 13
3
6
1
1
8
GAME 14
2
6
4
8
GAME 15
3
6
2
8
GAME 16
1
1
4
1
2
8
GAME 17...

output:

NRBBNKQR
RNBBQKRN
NRNKBRQB
BBRKRNNQ
BBNNRQKR
QBBRKNNR
NRBBNKQR
RBBNQKRN
BBNQRKNR
BBNRQKRN
NBBRKQNR
NRBBNKQR
BNRBNKRQ
BRNKQBNR
BBNNRQKR
NBBRKNQR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBNRNQKR
BBNNRKRQ
QBNRKNBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BQRNNBKR
BBNNRQKR
NBQRKNBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BQRNNBKR
BBNNRQKR
NBN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #10:

score: 0
Accepted
time: 151ms
memory: 22448kb

input:

GAME 1
3
2
6
3
8
GAME 2
2
2
1
5
8
GAME 3
4
4
4
4
8
GAME 4
4
5
2
8
GAME 5
3
2
4
4
8
GAME 6
5
5
2
8
GAME 7
2
1
1
4
3
8
GAME 8
3
2
5
2
8
GAME 9
4
2
5
8
GAME 10
3
3
4
2
3
8
GAME 11
4
3
1
3
8
GAME 12
3
4
3
2
8
GAME 13
3
1
2
2
1
8
GAME 14
4
3
1
5
8
GAME 15
5
3
2
1
8
GAME 16
4
5
1
8
GAME 17
5
5
3
8
GAME 18...

output:

NRBBNKQR
RBBNQKRN
BBNQRKNR
BBNNRQKR
BBRQNKNR
NRBBNKQR
RNBBQKRN
RNBQNBKR
BBRNNKRQ
BBRNQKNR
NRBBNKQR
BNRBNKRQ
BBNRNKRQ
BBNNRQKR
BBRNNKQR
NRBBNKQR
BNRBNKRQ
BBNNRKRQ
BQRBNKNR
NRBBNKQR
RBBNQKRN
BBNQRKNR
BRNBQKRN
BNRBQKNR
NRBBNKQR
BQRBNNKR
NRBBQNKR
BNRBNKQR
NRBBNKQR
RNBBQKRN
NRNKBRQB
BBNQRKNR
BBNNRQKR
QBR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #11:

score: 0
Accepted
time: 147ms
memory: 22580kb

input:

GAME 1
2
2
3
4
1
8
GAME 2
2
3
4
4
8
GAME 3
2
3
3
3
1
8
GAME 4
1
4
6
4
8
GAME 5
1
3
6
1
8
GAME 6
1
3
4
3
1
8
GAME 7
4
3
3
6
8
GAME 8
3
1
5
3
4
8
GAME 9
4
3
4
5
8
GAME 10
3
1
4
3
4
8
GAME 11
3
0
3
4
8
GAME 12
2
1
2
5
5
8
GAME 13
5
5
6
8
GAME 14
5
4
0
8
GAME 15
6
1
3
8
GAME 16
4
1
5
3
8
GAME 17
5
3
2
2...

output:

NRBBNKQR
RNBBQKRN
RNBQNBKR
BBNQRNKR
BBNNRKRQ
RQNBBNKR
NRBBNKQR
RNBBQKRN
RQKBNNBR
QNRBBKNR
RNQBBNKR
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBRNNQKR
BBNNRKRQ
RNNBBQKR
NRBBNKQR
BRNNKBQR
RNNQBBKR
BBNNRQKR
RQNNBBKR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBNNRKRQ
RNQNBBKR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBNRNQKR
BBNNRKRQ
RNNQBBKR
NRB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Extra Test:

score: 0
Extra Test Passed