QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224324#7179. Fischer's Chess Guessing GameDanilo21RE 1919ms10332kbC++173.3kb2023-10-23 01:18:262023-10-23 01:18:26

Judging History

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

  • [2023-10-23 01:18:26]
  • 评测
  • 测评结果:RE
  • 用时:1919ms
  • 内存:10332kb
  • [2023-10-23 01:18:26]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

const ll LINF = 4e18;
const int mxN = 1e3+10, INF = 2e9;
int n, m;
vector<string> a;
const vector<char> chars = {'K', 'Q', 'R', 'R', 'B', 'B', 'N', 'N'};
vector<int> bucket[mxN][10];

int Ask(string s){

    cout << s << endl;
    ri(x);
    return x;
}

vector<char> Ers(vector<char> v, int i){

    vector<char> temp;
    for (int j = 0; j < v.size(); j++)
        if (j^i) temp.pb(v[j]);
    return temp;
}

void Gen(string s, vector<char> v){

    if (v.empty()){
        int k;
        vector<int> r, b;
        for (int i = 0; i < s.size(); i++){
            if (s[i] == 'K') k = i;
            if (s[i] == 'R') r.pb(i);
            if (s[i] == 'B') b.pb(i);
        }
        if (r[0] < k && k < r[1] && b[0] % 2 != b[1] % 2)
            a.pb(s);
        return;
    }
    for (int i = 0; i < v.size(); i++)
        Gen(s + v[i], Ers(v, i));
}

void Unique(){

    set<string> st;
    for (string s : a) st.insert(s);
    a.clear();
    for (string s : st) a.pb(s);
}

int Cnt(string s, string t){

    int cnt = 0;
    for (int i = 0; i < 8; i++)
        if (s[i] == t[i]) cnt++;
    return cnt;
}

void Buckets(){

    for (int i = 0; i < a.size(); i++){
        for (int k = 0; k <= 8; k++)
            bucket[i][k].clear();
        for (int j = 0; j < a.size(); j++)
            bucket[i][Cnt(a[i], a[j])].pb(j);
    }
}

void Game(){

    Gen("", chars);
    Unique();
    int x = 0;
    while (x < 8){
        Buckets();
        int b = 0, mx = mxN;
        for (int i = 0; i < a.size(); i++){
            int cur = 0;
            for (int j = 0; j <= 8; j++)
                smax(cur, (int)bucket[i][j].size());
            if (cur < mx || (a.size() > 2 && cur == mx)){
                b = i;
                mx = cur;
            }
        }
        x = Ask(a[b]);
        vector<string> temp;
        for (int i : bucket[b][x])
            temp.pb(a[i]);
        a.clear();
        for (string s : temp) a.pb(s);
    }
    a.clear();
}

void Solve(){

    while (1){
        rs(text);
        if (text == "END") break;
        ri(n);
        Game();
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 21ms
memory: 10000kb

input:

GAME 1
3
1
6
5
8
END

output:

RQKNBBRN
NRBKQBRN
RKQBBRNN
RKNBBRQN
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 1905ms
memory: 10088kb

input:

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

output:

RQKNBBRN
NRBKQBRN
RKQBBRNN
RKNBBRQN
RKRBBQNN
RQKNBBRN
NRBKQBRN
RKQBBRNN
RKRBBNQN
RQKNBBRN
RNQKNBBR
BBRNNKRQ
QNBBRKRN
RKRBBNNQ
RQKNBBRN
RNQKNBBR
RQBBKNNR
RNBNKRQB
RKRBQNBN
RQKNBBRN
RNQKNBBR
QRBNNBKR
RBNKBNQR
RKRBNQBN
RQKNBBRN
RNBQKRNB
NNRBBKQR
RKNBQNBR
RKRBNNBQ
RQKNBBRN
RQBNKBNR
RQNKRBBN
RKRQBBNN
RQK...

result:

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

Test #3:

score: 0
Accepted
time: 1896ms
memory: 10320kb

input:

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

output:

RQKNBBRN
RNQKNBBR
QRBNNBKR
RBNKBNQR
RKQBBNNR
RQKNBBRN
RNQKNBBR
RQBBKNNR
RNBQKNRB
BQNRKBNR
RKNBBQNR
RQKNBBRN
RNQKNBBR
RQBBKNNR
RNBQKNRB
RKNBBNQR
RQKNBBRN
RNBQKRNB
NNRBBKQR
RKNBQNBR
RKNBNQBR
RKQBNNBR
RQKNBBRN
RNBQKRNB
NNRBBKQR
RKNBQNBR
RQKNBBRN
RNBQKRNB
NNRBBKQR
RKNBQNBR
RKNBNQBR
RQKNBBRN
RQBNKBNR
RQN...

result:

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

Test #4:

score: 0
Accepted
time: 1908ms
memory: 10024kb

input:

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

output:

RQKNBBRN
RQBNKBNR
RNKQRBBN
RBKRBQNN
QRKRBBNN
RQKNBBRN
RQBNKBNR
RNKBBNRQ
NRQKBBRN
NRKRBBQN
RQKNBBRN
NRBKQBRN
NRKQBBNR
NRKRBBNQ
RQKNBBRN
RNQKNBBR
QBBRKNRN
BBRNKRQN
QRKRBNNB
RQKNBBRN
RNQKNBBR
QBBRKNRN
NRNBBKRQ
NRKRBQNB
RQKNBBRN
RNQKNBBR
QBBRKNRN
NRKRBNQB
RQKNBBRN
NRBKQBRN
NRKQBBNR
RQBKNBNR
BRKRNBQN
QRK...

result:

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

Test #5:

score: 0
Accepted
time: 1904ms
memory: 10028kb

input:

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

output:

RQKNBBRN
RQBNKBNR
RQNKRBBN
RQKNBBRN
NRBKQBRN
NRKQBBNR
RKNRQBBN
RNQKRBBN
RQKNBBRN
RNQKNBBR
RNNQKBBR
RNBQNBKR
RNNKRBBQ
RQKNBBRN
RNQKNBBR
QRBNNBKR
RNKQRNBB
RQNKRNBB
RQKNBBRN
RNBQKRNB
RNBBQNKR
RNQKRNBB
RQKNBBRN
RNBQKRNB
RNBBQNKR
BNQRKBNR
NRBBKRQN
RNNKRQBB
RQKNBBRN
RNQKNBBR
RQBBKNNR
RNBNKRQB
RKBQNNRB
RBB...

result:

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

Test #6:

score: 0
Accepted
time: 1905ms
memory: 10084kb

input:

GAME 1
3
6
5
8
GAME 2
3
8
GAME 3
2
3
4
3
2
8
GAME 4
1
2
1
2
8
GAME 5
1
2
2
8
GAME 6
1
2
1
1
1
8
GAME 7
4
1
2
6
8
GAME 8
4
1
2
8
GAME 9
3
5
8
GAME 10
2
1
1
1
8
GAME 11
2
2
1
3
1
8
GAME 12
2
1
1
2
8
GAME 13
1
1
1
6
8
GAME 14
1
1
1
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
3...

output:

RQKNBBRN
NRBKQBRN
NRBQKBRN
QRBKNBRN
RQKNBBRN
NRBKQBRN
RQKNBBRN
RNQKNBBR
QRBNNBKR
QRNKBBNR
BQNRNBKR
NRBKNBRQ
RQKNBBRN
RNBQKRNB
BNRKQBNR
RKNRQNBB
QRBKNNRB
RQKNBBRN
RNBQKRNB
BNRKQBNR
NRBKQNRB
RQKNBBRN
RNBQKRNB
BNRKQBNR
RKNRQNBB
NBRNKRBQ
NRBKNQRB
RQKNBBRN
RQBNKBNR
RNKBBNRQ
NRQKBBRN
QRNKBBRN
RQKNBBRN
RQB...

result:

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

Test #7:

score: 0
Accepted
time: 1908ms
memory: 10332kb

input:

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

output:

RQKNBBRN
RNQKNBBR
BBRNNKRQ
RKBNRQNB
RKNBBRNQ
RBBQKRNN
RQKNBBRN
NRBKQBRN
QRNNBKRB
RNQKBBNR
RBBNKRQN
RQKNBBRN
RNQKNBBR
BBRNNKRQ
NQBRNKRB
RBBNKRNQ
RQKNBBRN
NRBKQBRN
RKQBBRNN
RKNRBBNQ
RBQNKRBN
RQKNBBRN
RNQKNBBR
RQBBKNNR
RKRNQNBB
NRBNQBKR
RBNQKRBN
RQKNBBRN
RNQKNBBR
RQBBKNNR
RKRNQNBB
RKNBRQBN
RBNNKRBQ
RQK...

result:

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

Test #8:

score: 0
Accepted
time: 1919ms
memory: 10284kb

input:

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

output:

RQKNBBRN
BBQRNNKR
QRBBNKNR
NRBBKNQR
QRNBKNBR
RQKNBBRN
BBQRNNKR
NRBBQNKR
NRQBKNBR
RQKNBBRN
BBQRNNKR
QRBKRNNB
NRNBQKBR
NRNBKQBR
RQKNBBRN
RNQKNBBR
QRBNNBKR
RBBNNQKR
QRNNKBBR
RQKNBBRN
RNQKNBBR
RNQBKRBN
NRQNKBBR
RQKNBBRN
RNBQKRNB
BNRKQBNR
NRBKQNRB
NRNQKBBR
RQKNBBRN
RNBQKRNB
QNBRKNRB
RKNQNRBB
BBRQKRNN
RQK...

result:

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

Test #9:

score: 0
Accepted
time: 1902ms
memory: 10040kb

input:

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

output:

RQKNBBRN
BBQRNNKR
QBRKNNBR
QBBRNKNR
QBBRKNNR
RQKNBBRN
BBQRNNKR
NRBBQNKR
NBNRQKBR
NBBRKQNR
RQKNBBRN
BBQRNNKR
QBRKNNBR
NBBRNKQR
NBBRKNQR
RQKNBBRN
BBQRNNKR
QBRKNNBR
QBNRNKBR
QBNRKNBR
RQKNBBRN
BBQRNNKR
BBNRNKQR
NBQRKNBR
RQKNBBRN
BBQRNNKR
NRBBQNKR
NBRQNKBR
BNRBNKQR
NBNRKQBR
RQKNBBRN
RNBQKRNB
QNBRKNRB
NRB...

result:

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

Test #10:

score: -100
Runtime Error

input:

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

output:

RQKNBBRN
BBQRNNKR
QBRKNNBR
QBBRNKNR
BBRQNKNR
RQKNBBRN
RNBQKRNB
NNRBBKQR
NRBKNBQR
QBNRBKNR
BBRNQKNR
RQKNBBRN
RNBQKRNB
BBRNQNKR
NBRNQKBR
BBRNNKQR
RQKNBBRN
RNBQKRNB
NNRBBKQR
NBRQBNKR
QRNBBKNR
BQRBNKNR
RQKNBBRN
BBQRNNKR
QRBBNKNR
NRBBKNQR
BNRBQKNR
RQKNBBRN
BBQRNNKR
NRBBQNKR
NBRQNKBR
BNRBNKQR
RQKNBBRN
RNQ...

result: