QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250265#7179. Fischer's Chess Guessing Gamekilo_tobo_tarjen#WA 138ms91864kbC++202.3kb2023-11-13 00:43:342023-11-13 00:43:36

Judging History

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

  • [2023-11-13 00:43:36]
  • 评测
  • 测评结果:WA
  • 用时:138ms
  • 内存:91864kb
  • [2023-11-13 00:43:34]
  • 提交

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: 100
Accepted
time: 138ms
memory: 91568kb

input:

GAME 1
1
0
2
4
8
END

output:

NRBBNKQR
BRNNKBQR
NBRKNQBR
QBRKBRNN
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 5 (1 test case)

Test #2:

score: -100
Wrong Answer
time: 138ms
memory: 91864kb

input:

GAME 1
1
0
2
4
8
GAME 2

output:

NRBBNKQR
BRNNKBQR
NBRKNQBR
QBRKBRNN
RKRBBQNN

result:

wrong answer (i) illegal position "" (game 2, guess 1) (test case 2)