QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#647229 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | AC ✓ | 184ms | 4180kb | C++20 | 4.0kb | 2024-10-17 12:52:43 | 2024-10-17 12:52:44 |
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 * log(x) * log(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);
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 4176kb
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: 103ms
memory: 4024kb
input:
GAME 1 6 4 4 5 0 8 GAME 2 4 4 2 4 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 2 0 8 GAME 7 4 6 4 8 GAME 8 3 0 3 6 1 8 GAME 9 4 4 4 2 1 8 GAME 10 4 4 4 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 3 1 8 GAME 16 2 4 1 2 0...
output:
RKNBBQNR RKNBBNQR RBNKBQNR RKBBNQNR BBNNQRKR RKRBBQNN RKNBBQNR RKNQBBRN RNKQBBNR RKNNBRQB BBNNQRKR RKRBBNQN RKNBBQNR RKNNBBQR RKBBQNNR RKRBBNNQ RKNBBQNR NRNBQKBR BNQBRKNR QRNNBBKR BBNNQRKR RKRBQNBN RKNBBQNR RKNQBBRN RKNBNRBQ RKNRNQBB BBNNQRKR RKRBNQBN RKNBBQNR NRNBQKBR RKNQRNBB RBNKRQBN BBNNQRKR RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 159ms
memory: 3988kb
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 3 8 GAME 13 4 3 1 2 1 8 GAME 14 2 3 2 4 1 8 GAME 15 3 0 5 8 GAME 16 1 2 2 1 3 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: 3960kb
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 2 3 0 8 GAME 13 3 2 1 0 1 8 GAME 14 1 2 3 0 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: 179ms
memory: 4152kb
input:
GAME 1 2 1 0 2 2 8 GAME 2 1 2 1 0 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 3 3 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 4 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 NRBBQKRN QBBNNRKR BBNNRQKR 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: 177ms
memory: 4084kb
input:
GAME 1 0 1 3 2 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 3 4 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 NBBRNKRQ BBQNRKRN 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: 183ms
memory: 4108kb
input:
GAME 1 2 4 1 4 2 8 GAME 2 1 0 5 2 3 8 GAME 3 2 3 1 4 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...
output:
RKNBBQNR RBBQNNKR NQBBRNKR RBBKNQRN BBNNQRKR RBBQKRNN RKNBBQNR NRKQNBBR RBBNQKRN BBNRQKRN BBNNQRKR RBBNKRQN RKNBBQNR RBBQNNKR QBNRNKBR RKBNNRQB BBNNQRKR RBBNKRNQ RKNBBQNR NRKQNBBR BQNRNKRB QBBNRNKR BBNNQRKR RBQNKRBN RKNBBQNR RBBQNNKR QBNRNKBR BBNNQRKR BBNNRKQR RBNQKRBN RKNBBQNR RBBQNNKR NRQBNKBR BNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 179ms
memory: 4180kb
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 5 3 2 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 GAM...
output:
RKNBBQNR NRNBQKBR QRNBKNBR RKNBBQNR RBBQNNKR NRQBNKBR NQRBNKBR BBNNQRKR NRQBKNBR RKNBBQNR RKNQBBRN RQBBNKNR BNNBRQKR BBNNQRKR NRNBKQBR RKNBBQNR RBBQNNKR BRKBNRNQ RNNKQRBB BBNRKRQN QRNNKBBR RKNBBQNR NRKQNBBR NNRQKBBR NBRQNKBR BBNNQRKR NRQNKBBR RKNBBQNR RBBQNNKR NRQBNKBR BNRBNKQR BBNNQRKR NRNQKBBR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 162ms
memory: 4176kb
input:
GAME 1 2 4 3 4 2 8 GAME 2 3 2 0 8 GAME 3 1 2 2 2 3 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 4 1 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 4 5 1 8 GAME 14 1 0 8 GAME 15 1 1 3 0 2 8 GAME 16 2 2 2 2 4 8...
output:
RKNBBQNR RBBQNNKR NQBBRNKR BBNRQNKR BBNNQRKR QBBRKNNR RKNBBQNR NRNBQKBR RKNQRNBB NBBRKQNR RKNBBQNR NRKQNBBR NRBBQKRN BRNQKNRB BBNNRKQR 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: 171ms
memory: 3940kb
input:
GAME 1 2 4 1 2 3 8 GAME 2 2 2 2 3 5 8 GAME 3 1 2 1 4 4 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 5 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...
output:
RKNBBQNR RBBQNNKR NQBBRNKR RBBKNQRN BBNNQRKR BBRQNKNR RKNBBQNR RBBQNNKR NRQBNKBR NQRNBBKR BBNNQRKR BBRNQKNR RKNBBQNR NRKQNBBR NRBBQKRN QBBNNRKR BBNNQRKR BBRNNKQR RKNBBQNR NRNBQKBR BNQBRKNR BBNQRKNR BBNNQRKR BQRBNKNR RKNBBQNR NRNBQKBR NRKBBNQR BNNBQRKR BBNNQRKR BNRBQKNR RKNBBQNR RBBQNNKR NRQBNKBR BNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 184ms
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 4 5 4 8 GAME 5 3 1 1 2 2 8 GAME 6 4 5 3 3 3 8 GAME 7 2 4 4 8 GAME 8 3 5 5 8 GAME 9 4 1 3 8 GAME 10 1 4 5 8 GAME 11 2 4 2 4 4 8 GAME 12 2 2 2 4 6 8 GAME 13 2 5 3 3 2 8 GAME 14 2 4 6 5 3 8 GAME 15 3 4 4 2 2 8 GAME 16 1 4 6 5 3 8 GAME ...
output:
RKNBBQNR RKNNBBQR RBKNBQNR RKNQBRNB BBNNQRKR RQNBBNKR RKNBBQNR RKNQBBRN QRNBBNKR NQNBBRKR BBNNQRKR RNQBBNKR RKNBBQNR RKNBBNQR RKNBBQRN RKNBBRNQ BBNNQRKR RNNBBQKR RKNBBQNR RKNQBBRN RNKQBBNR 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