QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#493108 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | WA | 175ms | 4036kb | C++20 | 4.0kb | 2024-07-26 19:37:24 | 2024-07-26 19:37:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 1;
const ll M = 1e9 + 7;
mt19937_64 rng(static_cast<ll>(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count()));
ll rand(ll l, ll r) {
return uniform_int_distribution<ll>(l, r)(rng);
}
string P = "BRKBNQRN";
string Q = "KNNBBRRQ";
string S[5] = {"RKNBBQNR"};
ll T[] = {(ll)0, (ll)300, (ll)15000, (ll)10000};
vector<string> v, res;
ll val[N];
ll cal(string &s, string &t) {
ll res = 0;
for (int i = 0; i <= 7; i ++)
if (s[i] == t[i]) res ++;
return res;
}
ll check(ll x, string &s) {
ll cnt = 0;
for (int i = 0; i <= 7; i ++) {
ll tmp = 0;
for (int j = 0; j < x; j ++)
tmp += (S[j][i] == s[i]);
cnt += tmp * 1e9;
}
return cnt;
}
void doTest(ll testID) {
while (true) {
bool nxt = 0;
string tmp; cin >> tmp;
if (tmp == "END") return;
cin >> tmp;
res.clear();
for (auto x: v) res.push_back(x);
/* BEGIN MESS 1*/
for (int i = 0; i <= -1; i ++) {
ll cnt = -1, tmp = 0;
for (int j = 0; j < min(T[i], (ll)res.size()); j ++) {
string cur = res[j]; tmp = 0;
for (auto y: res) tmp += check(i, cur);
if (tmp > cnt) {cnt = tmp; S[i] = cur;}
}
cout << S[i] << endl;
cin >> val[i]; if (val[i] == 8) {nxt = 1; break;}
vector<string> newRes;
for (auto x: res) if (cal(x, S[i]) == val[i]) newRes.push_back(x);
res = newRes;
// cout << "Debug: " << res.size() << endl;
}
if (nxt) continue;
/* BEGIN MESS 2*/
for (int i = 0; i <= 3; i ++) {
ll cnt = 1e18, tmp = 0;
for (int j = 0; j < min(T[i], (ll)res.size()); j ++) {
string cur = res[j];
map<ll, ll> m; for (auto y: res) m[cal(cur, y)] ++;
tmp = 0; for (auto [l, x]: m) tmp += x * x * x;
if (tmp < cnt) {cnt = tmp; S[i] = cur;}
}
val[i] = cal(P, S[i]);
// cout << "Debug: " << i << ' ' << S[i] << endl;
cout << S[i] << endl;
cin >> val[i]; if (val[i] == 8) {nxt = 1; break;}
vector<string> newRes;
for (auto x: res) if (cal(x, S[i]) == val[i]) newRes.push_back(x);
res = newRes;
// cout << "Debug: " << res.size() << endl;
}
if (nxt) continue;
/* BEGIN MESS 3*/
for (int i = 4; i <= 4; i ++) {
ll cnt = 0;
for (auto x: v) {
set<ll> s; for (auto y: res) s.insert(cal(x, y));
if (s.size() > cnt) {cnt = s.size(); S[i] = x;}
}
cout << S[i] << endl;
cin >> val[i]; if (val[i] == 8) {nxt = 1; break;}
vector<string> newRes;
for (auto x: res) if (cal(x, S[i]) == val[i]) newRes.push_back(x);
res = newRes;
}
if (nxt) break;
/*BEGIN MESS 4*/
// cout << "??? " << res.size() << endl;
cout << res[0] << endl;
cin >> val[5];
}
}
signed main() {
set<string> s;
string T = "KNNBBRRQ";
sort(T.begin(), T.end());
do {
vector<ll> b, r, k;
for (int i = 0; i <= 7; i ++) if (T[i] == 'B') b.push_back(i);
for (int i = 0; i <= 7; i ++) if (T[i] == 'K') k.push_back(i);
for (int i = 0; i <= 7; i ++) if (T[i] == 'R') r.push_back(i);
if ((b[1] - b[0]) % 2 == 0) continue;
if (r[0] > k[0] || r[1] < k[0]) continue;
s.insert(T);
} while(next_permutation(T.begin(), T.end()));
for (auto x: s) v.push_back(x);
ios_base::sync_with_stdio(0); cin.tie(0);
int test = 1;
// cin >> test;
for (int _ = 1; _ <= test; _ ++) doTest(test);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3960kb
input:
GAME 1 6 4 4 5 0 8 END
output:
RKNBBQNR RKNBBNQR RBNKBQNR RKBBNQNR BBNNQRKR RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: 0
Accepted
time: 97ms
memory: 3736kb
input:
GAME 1 6 4 4 5 0 8 GAME 2 4 4 2 5 0 8 GAME 3 5 3 5 8 GAME 4 3 3 1 0 1 8 GAME 5 4 3 5 5 0 8 GAME 6 3 2 4 5 0 8 GAME 7 4 6 4 8 GAME 8 3 0 3 6 1 8 GAME 9 4 4 4 8 GAME 10 4 4 4 5 0 8 GAME 11 5 4 3 3 1 8 GAME 12 3 0 2 3 2 8 GAME 13 2 3 2 1 2 8 GAME 14 2 3 4 2 2 8 GAME 15 2 4 1 4 1 8 GAME 16 2 2 3 2 1 8 G...
output:
RKNBBQNR RKNBBNQR RBNKBQNR RKBBNQNR BBNNQRKR RKRBBQNN RKNBBQNR RKNQBBRN RKBQNBNR RKNRBNQB BBNNQRKR RKRBBNQN RKNBBQNR RKNNBBQR RKBBQNNR RKRBBNNQ RKNBBQNR NRNBQKBR BNQBRKNR QRNNBBKR BBNNQRKR RKRBQNBN RKNBBQNR RKNQBBRN RKNBNRBQ RKNRNQBB BBNNQRKR RKRBNQBN RKNBBQNR NRNBQKBR RKNQRNBB RKNRNBBQ BBNNQRKR RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 148ms
memory: 3816kb
input:
GAME 1 6 6 8 GAME 2 8 GAME 3 6 8 GAME 4 4 2 3 4 1 8 GAME 5 5 4 5 8 GAME 6 6 5 5 8 GAME 7 5 6 8 GAME 8 6 5 4 8 GAME 9 5 8 GAME 10 3 2 3 5 2 8 GAME 11 4 5 2 8 GAME 12 4 4 4 4 4 8 GAME 13 4 3 1 2 1 8 GAME 14 2 1 2 0 1 8 GAME 15 3 0 5 8 GAME 16 1 2 2 1 2 8 GAME 17 2 2 2 1 1 8 GAME 18 1 3 5 3 1 8 GAME 19...
output:
RKNBBQNR RKNBBNQR RKQBBNNR RKNBBQNR RKNBBQNR RKNBBNQR RKNBBQNR RKNQBBRN QRNBBNKR RNNBQKBR BBNNQRKR RKQBNNBR RKNBBQNR RKNNBBQR RKNBBNRQ RKNBQNBR RKNBBQNR RKNBBNQR RKNBBQRN RKNBNQBR RKNBBQNR RKNNBBQR RKQNBBNR RKNBBQNR RKNBBNQR RKNBBQRN RKNQBBNR RKNBBQNR RKNNBBQR RKNBBQNR NRNBQKBR RKNQRNBB RKQBNRBN BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 159ms
memory: 4032kb
input:
GAME 1 2 1 3 3 0 8 GAME 2 1 4 3 4 0 8 GAME 3 2 1 4 1 0 8 GAME 4 2 0 3 1 0 8 GAME 5 3 2 1 2 0 8 GAME 6 1 3 2 3 0 8 GAME 7 0 3 4 8 GAME 8 0 5 3 2 1 8 GAME 9 0 4 2 2 0 8 GAME 10 0 4 2 3 0 8 GAME 11 0 6 4 8 GAME 12 1 5 3 5 0 8 GAME 13 3 2 1 0 1 8 GAME 14 1 2 3 3 1 8 GAME 15 2 0 3 3 2 8 GAME 16 1 4 2 8 G...
output:
RKNBBQNR RQBNNBKR NRKNBQRB RNKRBNQB BBNNQRKR QRKRBBNN RKNBBQNR NRKQNBBR NRBNQBKR NRKBQRBN BBNNQRKR NRKRBBQN RKNBBQNR RQBNNBKR NRKNBQRB BRNKNQRB BBNNQRKR NRKRBBNQ RKNBBQNR RQBNNBKR BRNQKRNB BRNBQKRN BBNNQRKR QRKRBNNB RKNBBQNR NRNBQKBR RKNQRNBB QNNRBBKR BBNNRKQR NRKRBQNB RKNBBQNR NRKQNBBR RBKQRNBN BRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 167ms
memory: 4036kb
input:
GAME 1 2 3 1 2 1 8 GAME 2 1 2 0 3 2 8 GAME 3 2 2 0 3 1 8 GAME 4 2 2 0 5 2 8 GAME 5 1 1 2 1 0 8 GAME 6 3 2 5 3 1 8 GAME 7 2 2 2 0 3 8 GAME 8 1 1 3 0 2 8 GAME 9 2 3 2 1 3 8 GAME 10 3 0 6 8 GAME 11 3 1 4 2 3 8 GAME 12 4 3 4 8 GAME 13 1 2 1 3 2 8 GAME 14 2 1 0 8 GAME 15 2 2 2 1 3 8 GAME 16 2 4 2 5 1 8 G...
output:
RKNBBQNR RQBNNBKR RKBNQNRB BRNNKBQR BBNNQRKR RQNKRBBN RKNBBQNR NRKQNBBR BRKNQRNB NQRKBBRN BBNQRKRN RNQKRBBN RKNBBQNR RQBNNBKR BBRQNKNR RKQNRNBB BBNNQRKR RNNKRBBQ RKNBBQNR RQBNNBKR BBRQNKNR RKQNRNBB BBNNRQKR RQNKRNBB RKNBBQNR NRKQNBBR BQRKNRNB BRNNQKRB BBNRNKRQ RNQKRNBB RKNBBQNR NRNBQKBR RKNQRNBB RKQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 164ms
memory: 3876kb
input:
GAME 1 0 1 3 2 0 8 GAME 2 0 3 3 8 GAME 3 0 2 5 4 0 8 GAME 4 0 2 3 2 0 8 GAME 5 0 4 2 8 GAME 6 1 3 0 1 0 8 GAME 7 2 1 3 1 1 8 GAME 8 1 3 1 2 0 8 GAME 9 2 1 4 4 1 8 GAME 10 2 0 3 3 1 8 GAME 11 1 2 2 0 1 8 GAME 12 3 3 0 2 1 8 GAME 13 2 3 0 6 3 8 GAME 14 3 4 2 4 4 8 GAME 15 2 3 0 8 GAME 16 2 4 5 2 1 8 G...
output:
RKNBBQNR NRKNQRBB NBBRNKRQ BBQNRKRN BBNNQRKR QRBKNBRN RKNBBQNR NRKNQRBB BRKNNBRQ NRBKQBRN RKNBBQNR NRKNQRBB NRBQKBRN BRKQNBRN BBNNQRKR NRBKNBRQ RKNBBQNR NRKNQRBB NRBQKBRN NBBNRKRQ BBNNRKQR QRBKNNRB RKNBBQNR NRKNQRBB NNRQKRBB NRBKQNRB RKNBBQNR NRKQNBBR RBKQRNBN BQRNNBKR BBNNRKQR NRBKNQRB RKNBBQNR RQB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 175ms
memory: 3992kb
input:
GAME 1 2 2 3 0 2 8 GAME 2 1 0 5 5 3 8 GAME 3 2 3 3 2 3 8 GAME 4 1 1 1 5 3 8 GAME 5 2 1 0 6 3 8 GAME 6 2 2 1 4 4 8 GAME 7 3 1 5 3 1 8 GAME 8 2 2 0 1 1 8 GAME 9 3 1 4 8 GAME 10 2 4 1 2 2 8 GAME 11 2 2 2 2 0 8 GAME 12 1 0 3 2 2 8 GAME 13 3 3 1 1 2 8 GAME 14 2 1 0 4 1 8 GAME 15 3 3 2 0 2 8 GAME 16 2 3 3...
output:
RKNBBQNR RQBNNBKR BBRQNKNR BRKBNNQR BBNNQRKR RBBQKRNN RKNBBQNR NRKQNBBR RBBNQKRN RBBNKNRQ BBNNQRKR RBBNKRQN RKNBBQNR RQBNNBKR RKBNQNRB RKQNRBBN BBNNQRKR RBBNKRNQ RKNBBQNR NRKQNBBR BQRKNRNB RBQKRNBN BBNNQRKR RBQNKRBN RKNBBQNR RQBNNBKR NRKNBQRB RBNKQRBN BBNNQRKR RBNQKRBN RKNBBQNR RQBNNBKR BBRQNKNR RBK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 166ms
memory: 3872kb
input:
GAME 1 3 5 8 GAME 2 2 1 2 2 1 8 GAME 3 4 1 2 5 2 8 GAME 4 2 3 1 6 2 8 GAME 5 1 5 4 8 GAME 6 2 2 2 4 2 8 GAME 7 1 1 4 8 GAME 8 0 2 2 5 4 8 GAME 9 1 0 2 4 4 8 GAME 10 2 1 0 2 2 8 GAME 11 1 0 1 2 1 8 GAME 12 2 0 4 2 2 8 GAME 13 1 0 1 3 3 8 GAME 14 1 1 5 4 2 8 GAME 15 0 3 2 2 3 8 GAME 16 0 3 1 0 3 8 GAM...
output:
RKNBBQNR NRNBQKBR QRNBKNBR RKNBBQNR RQBNNBKR NRKNBQRB BRNBNKRQ BBNNQRKR NRQBKNBR RKNBBQNR RKNQBBRN QNRBBKNR BRNBNQKR BBNNQRKR NRNBKQBR RKNBBQNR RQBNNBKR RKBNQNRB BRNNKBQR BBNQRKNR QRNNKBBR RKNBBQNR NRKQNBBR NQRKNBBR NRQNKBBR RKNBBQNR RQBNNBKR BBRQNKNR BNNRKBQR BBNNQRKR NRNQKBBR RKNBBQNR NRKQNBBR BQR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 158ms
memory: 3736kb
input:
GAME 1 2 2 3 2 5 8 GAME 2 3 2 0 2 2 8 GAME 3 1 2 0 1 2 8 GAME 4 2 1 0 3 3 8 GAME 5 1 3 3 3 2 8 GAME 6 3 4 2 2 3 8 GAME 7 2 3 1 3 1 8 GAME 8 2 4 2 1 1 8 GAME 9 1 3 0 2 1 8 GAME 10 2 2 1 0 2 8 GAME 11 2 3 0 3 2 8 GAME 12 1 4 3 2 1 8 GAME 13 1 2 0 2 1 8 GAME 14 1 0 8 GAME 15 1 1 1 2 3 8 GAME 16 2 2 2 0...
output:
RKNBBQNR RQBNNBKR BBRQNKNR BRKBNNQR BBNRKNQR QBBRKNNR RKNBBQNR NRNBQKBR RKNQRNBB QRKNBBNR BBNNQRKR NBBRKQNR RKNBBQNR NRKQNBBR BRKNQRNB NQRKBBRN BBNNQRKR NBBRKNQR RKNBBQNR RQBNNBKR NRKNBQRB RBNKQRBN BBNNQRKR QBNRKNBR RKNBBQNR NRKQNBBR RBKQRNBN BBRQNNKR BBNNQRKR NBQRKNBR RKNBBQNR NRNBQKBR NRKBBNQR BNN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 167ms
memory: 3964kb
input:
GAME 1 2 2 8 GAME 2 2 2 6 5 5 8 GAME 3 1 2 2 8 GAME 4 3 3 5 4 2 8 GAME 5 3 4 2 5 3 8 GAME 6 2 2 5 5 2 8 GAME 7 3 2 0 5 3 8 GAME 8 3 3 3 3 2 8 GAME 9 2 2 4 8 GAME 10 1 3 2 0 3 8 GAME 11 1 5 5 8 GAME 12 1 3 2 1 4 8 GAME 13 4 1 8 GAME 14 4 1 6 8 GAME 15 3 4 5 3 1 8 GAME 16 2 2 4 3 1 8 GAME 17 2 3 0 2 1...
output:
RKNBBQNR RQBNNBKR BBRQNKNR RKNBBQNR RQBNNBKR BBRQNKNR BBQRNKNR BBNNQRKR BBRNQKNR RKNBBQNR NRKQNBBR BRKNQRNB BBRNNKQR RKNBBQNR NRNBQKBR BNQBRKNR BBNQRKNR BBNNQRKR BQRBNKNR RKNBBQNR NRNBQKBR NRKBBNQR BNNBQRKR BBNNQRKR BNRBQKNR RKNBBQNR RQBNNBKR BBRQNKNR BBNRNKQR BBNNQRKR BNRBNKQR RKNBBQNR NRNBQKBR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: -100
Wrong Answer
time: 152ms
memory: 3804kb
input:
GAME 1 5 4 5 5 3 8 GAME 2 4 2 5 4 2 8 GAME 3 6 5 5 5 3 8 GAME 4 4 4 3 5 4 8 GAME 5 3 1 1 4 3 8 GAME 6 4 5 3 3 3 8 GAME 7 2 3 1 3 2 8 GAME 8 3 5 5 8 GAME 9 4 1 2 8 GAME 10 1 4 5 8 GAME 11 2 4 4 3 4 8 GAME 12 2 4 3 8 GAME 13 2 4 8 GAME 14 2 3 3 0 3 8 GAME 15 3 4 4 2 2 8 GAME 16 1 4 6 5 3 8 GAME 17 1 6...
output:
RKNBBQNR RKNNBBQR RKNBBNRQ RKNBQNBR BBNNQRKR RQNBBNKR RKNBBQNR RKNQBBRN QRNBBNKR NQNBBRKR BBNNQRKR RNQBBNKR RKNBBQNR RKNBBNQR RKNBBQRN RKNBNQBR BBNNQRKR RNNBBQKR RKNBBQNR RKNQBBRN RKBQNBNR RBNQBNKR BBNNQRKR RQNNBBKR RKNBBQNR NRNBQKBR RKBBNRQN RNNKBBRQ BBNNQRKR RNQNBBKR RKNBBQNR RKNQBBRN RBNKBQRN RKQ...
result:
wrong answer (i) illegal position "" (game 82, guess 1) (test case 82)