QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#750719#9537. Chinese ChessPlentyOfPenalty#RE 0ms0kbC++205.5kb2024-11-15 15:36:592024-11-15 15:37:01

Judging History

This is the latest submission verdict.

  • [2024-11-15 15:37:01]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-11-15 15:36:59]
  • Submitted

answer

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) ((void)(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
using lll = __int128;

const char name[] = {'J', 'S', 'C', 'M', 'X', 'B'};
int F[540][90];
vector<int> g[6][90];

int id(int x, int y) { return x * 9 + y; }
pair<int, int> pos(int k) { return make_pair(k / 9, k % 9); }

using status = bitset<540>;
status G[90][19];

unordered_map<status, pair<int, int>> mp;

int dfs(const status &u, int dep) {
  // cerr << "dfs " << u << endl;
  int c = -1;
  for (int i = u._Find_first(); i != 540; i = u._Find_next(i)) {
    if (c == -1) {
      c = i / 90;
    } else if (c != i / 90) {
      c = -2;
      break;
    }
  }
  if (c != -2) return 0;
  if (dep >= 2) return 114514;
  auto it = mp.find(u);
  if (it != mp.end()) {
    return it->second.first;
  }
  int mn = INT_MAX, cho = -1;
  for (int y = 0; y < 90; y++) {
    int mx = -1;
    for (int i = 0; i < 19; i++) {
      status v = G[y][i] & u;
      if (u == v || v.count() == 0) continue;
      mx = max(mx, dfs(v, dep + 1) + 1);
      // if (dep == 0) {
      //   log("finish y=%d i=%d mx=%d\n", y, i, mx);
      // }
    }
    // if (dep == 0) {
    //   log("finish y=%d mx=%d\n", y, mx);
    // }
    if (mx != -1 && mx < mn) {
      mn = mx;
      cho = y;
    }
  }
  // if (mn >= 3 && mn <= 100) {
  //   cerr << u << " " << mn << endl;
  // }
  mp[u] = make_pair(mn, cho);
  return mn;
}

int _x, _y, _c;
int ask(int i) {
#ifdef memset0
  return F[_c * 90 + id(_x, _y)][i];
#else
  auto [x, y] = pos(i);
  cout << "? " << x << " " << y << endl;
  cout << flush;
  int t;
  cin >> t;
  return t + 1;
#endif
}

int solve(status s) {
  int con = dfs(s, 0);
  int stp = con > 2 ? 3 : con;
  cout << stp << endl;
  cout << flush;
  mp.clear();
  while (con > 0) {
    if (con > 2) {
      int p = ask(0);
      s = G[0][p] & s;
      assert(dfs(s, 0) <= 2);
    } else {
      int i = mp[s].second;
      int p = ask(i);
      s = G[i][p] & s;
    }
    --stp;
    con = dfs(s, 0);
  }
  assert(stp >= 0);
  while (stp--) {
    ask(89);
  }
  int c = -1;
  for (int i = s._Find_first(); i != 540; i = s._Find_next(i)) {
    if (c == -1) {
      c = i / 90;
    } else if (c != i / 90) {
      c = -2;
      break;
    }
  }
  return c;
}

int main() {
#ifdef memset0
  freopen("C2.in", "r", stdin);
  // freopen("C.out", "w", stdout);
#endif
  cin.tie(0)->sync_with_stdio(0);

  for (int c = 0; c < 6; c++)
    for (int x = 0; x < 10; x++)
      for (int y = 0; y < 9; y++) {
        int i = id(x, y);
        auto push = [&](int x, int y) {
          if (x < 0 || y < 0 || x >= 10 || y >= 9) return;
          g[c][i].emplace_back(id(x, y));
        };
        if (c == 0) {
          push(x + 1, y);
          push(x - 1, y);
          push(x, y + 1);
          push(x, y - 1);
        } else if (c == 1) {
          push(x + 1, y + 1);
          push(x - 1, y + 1);
          push(x + 1, y - 1);
          push(x - 1, y - 1);
        } else if (c == 2) {
          for (int t = 0; t < 10; t++) {
            if (t != x) push(t, y);
          }
          for (int t = 0; t < 9; t++) {
            if (t != y) push(x, t);
          }
        } else if (c == 3) {
          push(x + 2, y + 1);
          push(x - 2, y + 1);
          push(x + 2, y - 1);
          push(x - 2, y - 1);
          push(x + 1, y + 2);
          push(x - 1, y + 2);
          push(x + 1, y - 2);
          push(x - 1, y - 2);
        } else if (c == 4) {
          push(x + 2, y + 2);
          push(x - 2, y + 2);
          push(x + 2, y - 2);
          push(x - 2, y - 2);
        } else {
          if (x <= 4) {
            push(x + 1, y);
          } else {
            push(x + 1, y);
            push(x, y - 1);
            push(x, y + 1);
          }
        }
      }

  for (int i = 0; i < 540; i++) {
    auto [x, y] = pos(i % 90);
    int c = i / 90;
    fill(all(F[i]), -1);
    F[i][id(x, y)] = 0;
    queue<int> q;
    q.push(id(x, y));
    // log("! c = %d x = %d y = %d\n", c, x, y);
    while (q.size()) {
      int u = q.front();
      q.pop();
      // log("F[%d][%d,%d] = %d\n", i, pos(u).first, pos(u).second, F[i][u]);
      for (int v : g[c][u])
        if (F[i][v] == -1) {
          F[i][v] = F[i][u] + 1;
          q.push(v);
        }
    }
  }
  for (int i = 0; i < 540; i++)
    for (int j = 0; j < 90; j++) {
      F[i][j]++;
      assert(F[i][j] < 19);
      G[j][F[i][j]].set(i);
    }

  // for (int i = 0; i < 540; i++)
  //   for (int j = 0; j < 90; j++) {
  //     printf("F[%d][%d] = %d\n", i, j, F[i][j]);
  //   }
  // return 0;

  // {
  //   status s;
  //   s.set();
  //   cout << dfs(s, 0) << endl;
  //   exit(0);
  // }

  status s;
  int n;
  cin >> n;
  vector<int> x(n), y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    for (int c = 0; c < 6; c++) {
      s.set(c * 90 + x[i] * 9 + y[i]);
    }
  }
  log(">> n=%d\n", n);
#ifdef memset0
  for (int i = 0; i < n; i++) {
    _x = x[i];
    _y = y[i];
    for (_c = 0; _c < 6; _c++) {
      log("test (%d, %d) %d\n", _x, _y, _c);
      int c = solve(s);
      log("test (%d, %d) %d -> %d\n", _x, _y, _c, c);
      assert(c == _c);
    }
  }
#else
  int res = solve(s);
  cout << "! " << name[res] << endl;
  cout << flush;
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

1
9 0
-1

output:

1
? 0 0
? 1 0

result: