QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#647235 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | AC ✓ | 177ms | 4044kb | C++20 | 4.0kb | 2024-10-17 12:54:07 | 2024-10-17 12:54:07 |
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 *sqrt(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) continue;
/*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: 1ms
memory: 3980kb
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: 104ms
memory: 4044kb
input:
GAME 1 6 4 4 5 0 8 GAME 2 4 4 4 8 GAME 3 5 3 5 8 GAME 4 3 3 1 0 1 8 GAME 5 4 3 1 4 0 8 GAME 6 3 2 4 2 0 8 GAME 7 4 6 4 8 GAME 8 3 0 3 6 1 8 GAME 9 4 4 2 2 1 8 GAME 10 4 4 2 4 0 8 GAME 11 5 4 5 3 1 8 GAME 12 3 0 2 3 2 8 GAME 13 2 3 2 5 0 8 GAME 14 2 1 0 2 1 8 GAME 15 2 2 2 2 0 8 GAME 16 2 4 2 0 0 8 G...
output:
RKNBBQNR RKNBBNQR RBNKBQNR RKBBNQNR BBNNQRKR RKRBBQNN RKNBBQNR RKNQBBRN RNKBBQRN RKRBBNQN RKNBBQNR RKNNBBQR RKBBQNNR RKRBBNNQ RKNBBQNR NRNBQKBR BNQBRKNR QRNNBBKR BBNNQRKR RKRBQNBN RKNBBQNR RKNQBBRN RBNKBNQR RKBBQRNN BBNNQRKR RKRBNQBN RKNBBQNR NRNBQKBR RKNQRNBB RBNKRQBN BBNNQRKR RKRBNNBQ RKNBBQNR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 154ms
memory: 3968kb
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 2 5 3 8 GAME 6 6 5 5 4 2 8 GAME 7 5 6 8 GAME 8 6 5 4 8 GAME 9 5 8 GAME 10 3 2 3 1 2 8 GAME 11 4 5 2 8 GAME 12 4 4 1 4 4 8 GAME 13 4 3 3 8 GAME 14 2 3 2 4 1 8 GAME 15 3 0 5 8 GAME 16 1 2 2 1 2 8 GAME 17 2 3 4 2 1 8 GAME 18 1 3 5 3 1 8 GAM...
output:
RKNBBQNR RKNBBNQR RKQBBNNR RKNBBQNR RKNBBQNR RKNBBNQR RKNBBQNR RKNQBBRN QRNBBNKR RBQKBNNR BBNNQRKR RKQBNNBR RKNBBQNR RKNNBBQR RBKNBQNR RKNBBNRQ BBNNQRKR RKNBQNBR RKNBBQNR RKNBBNQR RKNBBQRN RKNBBRNQ BBNNQRKR RKNBNQBR RKNBBQNR RKNNBBQR RKQNBBNR RKNBBQNR RKNBBNQR RKNBBQRN RKNQBBNR RKNBBQNR RKNNBBQR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 175ms
memory: 3744kb
input:
GAME 1 2 0 3 1 0 8 GAME 2 1 4 3 1 0 8 GAME 3 2 0 1 1 0 8 GAME 4 2 1 3 2 0 8 GAME 5 3 2 1 2 0 8 GAME 6 1 3 2 2 0 8 GAME 7 0 3 2 3 0 8 GAME 8 0 5 2 3 1 8 GAME 9 0 4 2 2 0 8 GAME 10 0 4 2 3 0 8 GAME 11 0 6 5 8 GAME 12 1 5 3 3 0 8 GAME 13 3 2 1 0 1 8 GAME 14 1 2 3 3 1 8 GAME 15 2 1 6 8 GAME 16 1 4 2 8 G...
output:
RKNBBQNR RBBQNNKR QNRBBKRN BNRBKRNQ BBNNQRKR QRKRBBNN RKNBBQNR NRKQNBBR NRBNQBKR BNRQNBKR BBNNQRKR NRKRBBQN RKNBBQNR RBBQNNKR QNRBBKRN BRNNKQRB BBNNQRKR NRKRBBNQ RKNBBQNR RBBQNNKR BRKBNRNQ BRQNKBNR 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: 171ms
memory: 3708kb
input:
GAME 1 2 1 0 2 2 8 GAME 2 1 2 0 1 1 8 GAME 3 2 1 1 5 1 8 GAME 4 2 2 1 0 1 8 GAME 5 1 1 1 3 1 8 GAME 6 3 2 5 4 1 8 GAME 7 2 3 1 8 GAME 8 1 1 1 4 2 8 GAME 9 2 4 1 5 2 8 GAME 10 3 0 6 5 2 8 GAME 11 3 1 4 2 3 8 GAME 12 4 3 5 4 3 8 GAME 13 1 2 1 3 2 8 GAME 14 2 2 1 0 4 8 GAME 15 2 3 4 1 3 8 GAME 16 2 3 1...
output:
RKNBBQNR RBBQNNKR BRKBNRNQ NNRKBBQR BBNNRKRQ RQNKRBBN RKNBBQNR NRKQNBBR BRKNQRNB NBRQBKRN BBNNRKQR RNQKRBBN RKNBBQNR RBBQNNKR BRKBNRNQ RNNKQRBB BBNNQRKR RNNKRBBQ RKNBBQNR RBBQNNKR NRQBNKBR BNRQKBNR BBNNQRKR RQNKRNBB RKNBBQNR NRKQNBBR BQNRNKRB RNBKQBRN BBNNRKQR RNQKRNBB RKNBBQNR NRNBQKBR RKNQRNBB RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 170ms
memory: 3792kb
input:
GAME 1 0 1 3 1 0 8 GAME 2 0 3 2 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 0 4 2 1 8 GAME 8 1 3 1 2 0 8 GAME 9 2 0 2 4 1 8 GAME 10 2 1 1 3 1 8 GAME 11 1 2 2 0 1 8 GAME 12 3 3 0 8 GAME 13 2 2 4 3 2 8 GAME 14 3 4 2 4 4 8 GAME 15 2 2 3 2 3 8 GAME 16 2 3 3 1 4 8 G...
output:
RKNBBQNR NRKNQRBB NNBRKBRQ BBRNKNRQ BBNNQRKR QRBKNBRN RKNBBQNR NRKNQRBB BRQNNKRB NRBKQBRN RKNBBQNR NRKNQRBB NRBQKBRN BRKQNBRN BBNNQRKR NRBKNBRQ RKNBBQNR NRKNQRBB NRBQKBRN NBBNRKRQ BBNNRKQR QRBKNNRB RKNBBQNR NRKNQRBB NNRQKRBB NRBKQNRB RKNBBQNR NRKQNBBR RBKQRNBN BQRNNBKR BBNNRKQR NRBKNQRB RKNBBQNR RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 176ms
memory: 3740kb
input:
GAME 1 2 4 0 8 GAME 2 1 0 5 2 3 8 GAME 3 2 3 1 5 3 8 GAME 4 1 1 0 2 3 8 GAME 5 2 3 3 3 2 8 GAME 6 2 2 1 1 4 8 GAME 7 3 1 5 3 1 8 GAME 8 2 2 1 2 1 8 GAME 9 3 1 4 4 1 8 GAME 10 2 2 0 2 2 8 GAME 11 2 3 0 4 1 8 GAME 12 1 0 3 2 2 8 GAME 13 3 3 1 1 2 8 GAME 14 2 1 2 1 1 8 GAME 15 3 3 2 3 2 8 GAME 16 2 1 1...
output:
RKNBBQNR RBBQNNKR BRQBNNKR RBBQKRNN RKNBBQNR NRKQNBBR RBBNQKRN BBNRQKRN BBNNQRKR RBBNKRQN RKNBBQNR RBBQNNKR QBNRNKBR RBBKQRNN BBNNQRKR RBBNKRNQ RKNBBQNR NRKQNBBR BQNRNKRB QBBNRNKR BBNNQRKR RBQNKRBN RKNBBQNR RBBQNNKR QBNRNKBR BBNNQRKR BBNNRKQR RBNQKRBN RKNBBQNR RBBQNNKR NRQBNKBR BNRQKBNR BBNNQRKR RBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 175ms
memory: 3904kb
input:
GAME 1 3 5 8 GAME 2 2 2 6 4 1 8 GAME 3 4 1 2 4 2 8 GAME 4 2 1 1 2 2 8 GAME 5 1 5 4 8 GAME 6 2 2 4 1 2 8 GAME 7 1 1 1 1 4 8 GAME 8 0 2 2 5 4 8 GAME 9 1 0 2 4 4 8 GAME 10 2 0 3 6 2 8 GAME 11 1 0 1 2 1 8 GAME 12 2 0 3 8 GAME 13 1 0 1 3 3 8 GAME 14 1 1 2 8 GAME 15 0 3 3 3 3 8 GAME 16 0 3 1 5 3 8 GAME 17...
output:
RKNBBQNR NRNBQKBR QRNBKNBR RKNBBQNR RBBQNNKR NRQBNKBR NQRBNKBR BBNNQRKR NRQBKNBR RKNBBQNR RKNQBBRN RQBBNKNR BNNBRQKR BBNNQRKR NRNBKQBR RKNBBQNR RBBQNNKR BRKBNRNQ RNNKQRBB BBNRKRQN QRNNKBBR RKNBBQNR NRKQNBBR BRKNNBQR NRQNKBBR RKNBBQNR RBBQNNKR NRQBNKBR BNRBNKQR BBNNQRKR NRNQKBBR RKNBBQNR NRKQNBBR BQN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 156ms
memory: 3792kb
input:
GAME 1 2 4 2 3 3 8 GAME 2 3 2 0 8 GAME 3 1 2 0 2 2 8 GAME 4 2 3 6 4 3 8 GAME 5 1 3 3 3 2 8 GAME 6 3 4 2 2 3 8 GAME 7 2 2 1 5 1 8 GAME 8 2 2 2 2 2 8 GAME 9 1 3 0 2 1 8 GAME 10 2 1 0 3 3 8 GAME 11 2 1 0 3 2 8 GAME 12 1 4 3 3 1 8 GAME 13 1 2 0 5 1 8 GAME 14 1 0 8 GAME 15 1 1 3 0 2 8 GAME 16 2 2 2 3 0 8...
output:
RKNBBQNR RBBQNNKR BRQBNNKR NBBNRQKR BBNQRKNR QBBRKNNR RKNBBQNR NRNBQKBR RKNQRNBB NBBRKQNR RKNBBQNR NRKQNBBR BRKNQRNB NBRQBKRN BBNNQRKR NBBRKNQR RKNBBQNR RBBQNNKR QBNRNKBR BBNRNKQR BBNNQRKR QBNRKNBR RKNBBQNR NRKQNBBR RBKQRNBN BBRQNNKR BBNNQRKR NBQRKNBR RKNBBQNR NRNBQKBR NRKBBNQR BNNBQRKR BBNNQRKR NBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 164ms
memory: 3764kb
input:
GAME 1 2 4 3 6 3 8 GAME 2 2 2 2 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 4 8 GAME 7 3 2 0 3 3 8 GAME 8 3 3 3 3 2 8 GAME 9 2 2 3 4 3 8 GAME 10 1 3 2 1 3 8 GAME 11 1 5 2 8 GAME 12 1 3 2 1 4 8 GAME 13 4 1 4 4 1 8 GAME 14 4 1 5 5 1 8 GAME 15 3 4 5 2 1 8 GAME 16 2 2 5 3 1 8 GAME ...
output:
RKNBBQNR RBBQNNKR BRQBNNKR BBRQKNNR BBNNQRKR BBRQNKNR RKNBBQNR RBBQNNKR NRQBNKBR BBRNQKNR RKNBBQNR NRKQNBBR BRKNQRNB BBRNNKQR RKNBBQNR NRNBQKBR BNQBRKNR BBNQRKNR BBNNQRKR BQRBNKNR RKNBBQNR NRNBQKBR NRKBBNQR BNNBQRKR BBNNQRKR BNRBQKNR RKNBBQNR RBBQNNKR NRQBNKBR BNRBNKQR RKNBBQNR NRNBQKBR RKNQRNBB NBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 177ms
memory: 3908kb
input:
GAME 1 5 4 3 3 3 8 GAME 2 4 2 5 4 2 8 GAME 3 6 5 5 4 3 8 GAME 4 4 4 2 5 4 8 GAME 5 3 1 1 2 2 8 GAME 6 4 5 3 3 3 8 GAME 7 2 4 8 GAME 8 3 5 5 8 GAME 9 4 1 3 8 GAME 10 1 4 5 8 GAME 11 2 4 5 8 GAME 12 2 2 2 4 6 8 GAME 13 2 5 3 3 2 8 GAME 14 2 4 5 3 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 RBKNBQNR RKNQBRNB BBNNQRKR RQNBBNKR RKNBBQNR RKNQBBRN QRNBBNKR NQNBBRKR BBNNQRKR RNQBBNKR RKNBBQNR RKNBBNQR RKNBBQRN RKNBBRNQ BBNNQRKR RNNBBQKR RKNBBQNR RKNQBBRN RNKBBQRN RBNQBNKR BBNNQRKR RQNNBBKR RKNBBQNR NRNBQKBR RKBBNRQN RBNKBNRQ BBNNRKQR RNQNBBKR RKNBBQNR RKNQBBRN RBNKBQRN RKQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed