QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224327#7179. Fischer's Chess Guessing GameDanilo21RE 1983ms9972kbC++173.2kb2023-10-23 01:19:512023-10-23 01:19:51

Judging History

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

  • [2023-10-23 01:19:51]
  • 评测
  • 测评结果:RE
  • 用时:1983ms
  • 内存:9972kb
  • [2023-10-23 01:19:51]
  • 提交

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){
                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: 25ms
memory: 9856kb

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: 1980ms
memory: 9912kb

input:

GAME 1
3
1
6
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
8
GAME 11
3
0
1
8
GAME 12
3
0
2
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
8
GAME 17
2
2
2
8
GAME 18
2
3
2
3...

output:

RQKNBBRN
NRBKQBRN
RKQBBRNN
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
RQKNBBRN
RQK...

result:

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

Test #3:

score: 0
Accepted
time: 1944ms
memory: 9840kb

input:

GAME 1
2
3
1
4
4
8
GAME 2
2
2
4
1
8
GAME 3
2
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
5
3
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
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
3
8
GAM...

output:

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

result:

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

Test #4:

score: 0
Accepted
time: 1962ms
memory: 9916kb

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
8
GAME 8
3
5
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
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 18
3
2...

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

result:

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

Test #5:

score: 0
Accepted
time: 1950ms
memory: 9876kb

input:

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

output:

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

result:

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

Test #6:

score: 0
Accepted
time: 1956ms
memory: 9872kb

input:

GAME 1
3
6
5
8
GAME 2
3
8
GAME 3
2
3
4
3
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
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
8
G...

output:

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

result:

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

Test #7:

score: 0
Accepted
time: 1983ms
memory: 9888kb

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
8
GAME 6
2
2
2
3
3
8
GAME 7
3
2
0
2
8
GAME 8
2
2
4
4
8
GAME 9
1
6
5
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
8
GAME 18
1
6
4
8
G...

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
RBNQKRBN
RQKNBBRN
RNQKNBBR
RQBBKNNR
RKRNQNBB
RKNBRQBN
RBNNKRBQ
RQKNBBRN
NRB...

result:

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

Test #8:

score: 0
Accepted
time: 1982ms
memory: 9932kb

input:

GAME 1
0
2
4
5
8
GAME 2
0
3
5
3
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
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
1
8
GAME 15
1
4
3
2
1
8
GAME 16
2
1
3
0
8
GAME 17
1
3
0
3
8
G...

output:

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

result:

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

Test #9:

score: 0
Accepted
time: 1952ms
memory: 9972kb

input:

GAME 1
0
4
4
6
8
GAME 2
0
3
3
4
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
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
8
GAME 11
2
3
2
0
8
GAME 12
1
2
3
2
4
8
GAME 13
3
3
1
2
8
GAME 14
4
3
2
1
8
GAME 15
3
2
3
2
8
GAME 16
5
3
5
4
8
GAME 17
4
1
3
8
GAM...

output:

RQKNBBRN
BBQRNNKR
QBRKNNBR
QBBRNKNR
QBBRKNNR
RQKNBBRN
BBQRNNKR
NRBBQNKR
NBNRQKBR
NBRQKNBR
NBBRKQNR
RQKNBBRN
BBQRNNKR
QBRKNNBR
NBBRNKQR
NBBRKNQR
RQKNBBRN
BBQRNNKR
QBRKNNBR
QBNRNKBR
QBNRKNBR
RQKNBBRN
BBQRNNKR
BBNRNKQR
NBQRKNBR
RQKNBBRN
BBQRNNKR
NRBBQNKR
NBRQNKBR
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
4

output:

RQKNBBRN
BBQRNNKR
QBRKNNBR
QBBRNKNR
BBRQNKNR
RQKNBBRN
RNBQKRNB
NNRBBKQR
NRBKNBQR
QBNRBKNR
BQNBRKNR
BBRNQKNR

result: