QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250264#7185. Poor Studentskilo_tobo_tarjen#WA 137ms91532kbC++202.3kb2023-11-13 00:43:162023-11-13 00:43:17

Judging History

你现在查看的是最新测评结果

  • [2023-11-13 00:43:17]
  • 评测
  • 测评结果:WA
  • 用时:137ms
  • 内存:91532kb
  • [2023-11-13 00:43:16]
  • 提交

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