QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#318947 | #7179. Fischer's Chess Guessing Game | PhanDinhKhoi# | TL | 11ms | 3752kb | C++20 | 3.2kb | 2024-02-01 11:49:42 | 2024-02-01 11:49:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz
#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y)
{
x = y;
return true;
}
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y)
{
x = y;
return true;
}
return false;
}
const int MOD = 1e9 + 7; //998244353
template<class X, class Y>
void add(X &x, const Y &y) {
x = (x + y);
if(x >= MOD) x -= MOD;
}
template<class X, class Y>
void sub(X &x, const Y &y) {
x = (x - y);
if(x < 0) x += MOD;
}
/* Author : Le Ngoc Bao Anh, DUT, Da Nang */
const ll INF = 1e9;
const int N = 1e5 + 10;
int B[N];
void BaoJiaoPisu() {
string a = "RQKBBNRN";
vector<string> cand;
sort(all(a));
int sz = 8;
do {
bool ok = true;
int G = 0, cnt = 0;
for(int i = 0; i < 8; i++) {
cnt += (a[i] == 'R');
if(a[i] == 'K') ok &= (cnt == 1);
if(a[i] == 'B') G += (i & 1);
}
ok &= (G == 1);
if(ok) cand.pb(a);
} while(next_permutation(all(a)));
auto cnt = [&](string a, string b) -> int {
int ans = 0;
for(int i = 0; i < 8; i++) {
ans += (a[i] == b[i]);
}
return ans;
};
auto get_opt = [&](vector<string> curr) -> string {
string ans = "";
int opt = INF;
for(int i = 0; i < curr.size(); i++) {
for(int j = 0; j <= 8; j++) B[j] = 0;
int T = 0;
for(int j = 0; j < curr.size(); j++) {
++B[cnt(curr[i], curr[j])];
}
for(int j = 0; j <= 8; j++) maximize(T, B[j]);
if(minimize(opt, T)) ans = curr[i];
}
return ans;
};
string root = get_opt(cand);
while(true) {
string s; cin >> s;
if(s == "END") break;
int x; cin >> x;
vector<string> curr = cand;
while(true) {
string ask = (curr.size() == 960 ? root : get_opt(curr));
cout << ask << endl;
int x; cin >> x;
if(x == 8) break;
vector<string> ncurr;
for(auto p : curr) {
if(cnt(p, ask) == x) ncurr.pb(p);
}
curr = ncurr;
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#else
//online
#endif
int tc = 1, ddd = 0;
// cin >> tc;
while(tc--) {
//ddd++;
//cout << "Case #" << ddd << ": ";
BaoJiaoPisu();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 3752kb
input:
GAME 1 1 2 2 1 2 8 END
output:
NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN QNRNBKRB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: -100
Time Limit Exceeded
input:
GAME 1 1 2 2 1 2 8 GAME 2 2 1 0 1 2 8 GAME 3 1 2 2 0 3 8 GAME 4 1 2 1 1 3 8 GAME 5 2 2 0 3 0 8 GAME 6 2 1 2 1 3 8 GAME 7 0 2 3 4 3 8 GAME 8 1 2 1 0 3 8 GAME 9 0 3 1 2 8 GAME 10 0 3 3 3 8 GAME 11 0 5 3 2 8 GAME 12 1 1 1 4 8 GAME 13 1 2 2 3 4 8 GAME 14 0 4 3 4 8 GAME 15 1 2 1 0 1 8 GAME 16 1 1 3 2 2 8...
output:
NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN QNRNBKRB RKRBBQNN NRBBNKQR RBBNKQNR QRKNNRBB NBNRBKRQ BQNBRNKR RKRBBNQN NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN RBKNBQNR RKRBBNNQ NRBBNKQR BNRKQBNR RNBQKRNB BBNQRNKR QBRKNRBN RKRBQNBN NRBBNKQR RBBNKQNR NBNQBRKR BRKBRQNN QRBKRNNB RKRBNQBN NRBBNKQR RBBNKQNR QRKNNRBB NRK...