QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#250264 | #7185. Poor Students | kilo_tobo_tarjen# | WA | 137ms | 91532kb | C++20 | 2.3kb | 2023-11-13 00:43:16 | 2023-11-13 00:43:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
vector<int> ve[maxn];
int dep[maxn];
string s[maxn], q[maxn];
vector<string> all;
void getlegal() {
vector<int> a(8);
iota(a.begin(), a.end(), 0);
string s = "RQKBBNRN";
sort(s.begin(), s.end());
do {
string ss;
for (int i = 0; i < 8; i++) ss.push_back(s[a[i]]);
bool flag = true;
int g = 0, k;
vector<int> v;
for (int i = 0; i < 8; i++) {
if (ss[i] == 'K') k = i;
if (ss[i] == 'R') v.push_back(i);
if (ss[i] == 'B') g += i;
}
if (g % 2 == 1 && k > v[0] && k < v[1]) all.push_back(ss);
} while (next_permutation(a.begin(), a.end()));
sort(all.begin(), all.end());
all.resize(unique(all.begin(), all.end()) - all.begin());
}
int f(string s1, string s2) {
int res = 0;
for (int i = 0; i < 8; i++) res += s1[i] == s2[i];
return res;
}
int tot = 0;
int dfs(vector<string> &now, int d) {
if ((int)now.size() == 1) {
s[++tot] = now[0];
return tot;
}
if (now.empty()) return -1;
assert(d <= 5);
int id = ++tot;
int mi = 1e9;
string tt;
for (auto &it : all) {
vector<string> p[9];
int g = 0;
for (auto &t : now) {
int z = f(it, t);
p[z].push_back(t);
g = max((int)p[z].size(), g);
}
if (g < mi) {
mi = g;
tt = it;
}
}
vector<string> p[9];
for (auto &t : now) {
int z = f(tt, t);
p[z].push_back(t);
}
q[id] = tt;
for (int i = 0; i < 9; i++) ve[id].push_back(dfs(p[i], d + 1));
// cout<<"id="<<id<<"\n";
// for(auto it:ve[id])cout<<it<<" ";;cout<<"\n";
return id;
}
void init() {
getlegal();
dfs(all, 1);
}
struct gettime {
clock_t star, ends;
void begin() { star = clock(); }
void end() {
ends = clock();
cout << "Running Time : " << (double)(ends - star) / CLOCKS_PER_SEC << endl;
}
} tim;
int query(string s) {
cout << s << endl;
int x;
cin >> x;
return x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
tim.begin();
init();
string z;
cin >> z;
int T;
cin >> T;
while (T--) {
int now = 1;
while (s[now].empty()) {
// cout<<"now="<<now<<"\n";
int g = query(q[now]);
now = ve[now][g];
}
query(s[now]);
}
cin >> z;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 137ms
memory: 91532kb
input:
6 2 1 2 1 3 1 4 1 5 1 6 1 7 3 4
output:
NRBBNKQR BRNNKBQR BNRBKRQN BRKQNBNR BBNNRKRQ QRKNBRNB NRBBNKQR BRNNKBQR BBNQRKNR BRQNKBRN
result:
wrong output format NRBBNKQR is not a valid integer