QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#702269#9537. Chinese ChessHoMaMaOvO (Riku Kawasaki, Masaki Nishimoto, Yui Hosaka)#RE 4ms69852kbC++145.5kb2024-11-02 15:36:222024-11-02 15:36:23

Judging History

This is the latest submission verdict.

  • [2024-11-02 15:36:23]
  • Judged
  • Verdict: RE
  • Time: 4ms
  • Memory: 69852kb
  • [2024-11-02 15:36:22]
  • Submitted

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr int K = 6;
constexpr int M = 10;
constexpr int N = 9;
const string STR = "JSCMXB";

int id(int x, int y) {
  return x * N + y;
}

int dist[K][M][N][M][N];

int fs[1 << 24];
bool check(const vector<int> &ss, const vector<int> &ts) {
  const int P = ss.size();
  const int Q = ts.size();
  auto calc = [&](int k, int p) -> int {
    int z = 0;
    for (int q = 0; q < Q; ++q) {
      z |= (1 + dist[k][ss[p] / N][ss[p] % N][ts[q] / N][ts[q] % N]) << (q * 6);
    }
    return z;
  };
  for (int k = 0; k < K; ++k) for (int p = 0; p < P; ++p) {
    const int z = calc(k, p);
    if (!~fs[z]) fs[z] = k;
    if (fs[z] != k) {
      for (int kk = 0; kk <= k; ++kk) for (int pp = 0; pp < P; ++pp) fs[calc(kk, pp)] = -1;
      return false;
    }
  }
  for (int k = 0; k < K; ++k) for (int p = 0; p < P; ++p) fs[calc(k, p)] = -1;
  return true;
}

bool solve(const vector<int> &ss, const vector<int> &ts) {
  if (!check(ss, ts)) return false;
  const int P = ss.size();
  const int Q = ts.size();
  printf("%d\n", Q); fflush(stdout);
  vector<int> ds(Q);
  for (int q = 0; q < Q; ++q) {
    printf("? %d %d\n", ts[q] / N, ts[q] % N); fflush(stdout);
    scanf("%d", &ds[q]);
  }
  for (int k = 0; k < K; ++k) for (int p = 0; p < P; ++p) {
    bool ok = true;
    for (int q = 0; q < Q; ++q) {
      ok = ok && (ds[q] == dist[k][ss[p] / N][ss[p] % N][ts[q] / N][ts[q] % N]);
    }
    if (ok) {
      printf("! %c\n", STR[k]); fflush(stdout);
      return true;
    }
  }
  assert(false);
  return true;
}

int main() {
  memset(dist, ~0, sizeof(dist));
  for (int k = 0; k < K; ++k) {
    for (int sx = 0; sx < M; ++sx) for (int sy = 0; sy < N; ++sy) {
      auto d = dist[k][sx][sy];
      queue<pair<int, int>> que;
      d[sx][sy] = 0;
      que.emplace(sx, sy);
      for (; que.size(); ) {
        const int x = que.front().first;
        const int y = que.front().second;
        que.pop();
        auto f = [&](int xx, int yy) -> void {
          if (0 <= xx && xx < M && 0 <= yy && yy < N) {
            if (!~d[xx][yy]) {
              d[xx][yy] = d[x][y] + 1;
              que.emplace(xx, yy);
            }
          }
        };
        const int r = x;
        const int c = y;
        switch (STR[k]) {
          case 'J': {
            f(r + 1, c); f(r - 1, c); f(r, c + 1); f(r, c - 1);
          } break;
          case 'S': {
            f(r + 1, c + 1); f(r + 1, c - 1); f(r - 1, c + 1); f(r - 1, c - 1);
          } break;
          case 'C': {
            for (int rr = 0; rr < M; ++rr) f(rr, c);
            for (int cc = 0; cc < N; ++cc) f(r, cc);
          } break;
          case 'M': {
            f(r + 2, c + 1); f(r + 2, c - 1); f(r - 2, c + 1); f(r - 2, c - 1);
            f(r + 1, c + 2); f(r + 1, c - 2); f(r - 1, c + 2); f(r - 1, c - 2);
          } break;
          case 'X': {
            f(r + 2, c + 2); f(r + 2, c - 2); f(r - 2, c + 2); f(r - 2, c - 2);
          } break;
          case 'B': {
            if (r <= 4) {
              f(r + 1, c);
            } else {
              f(r + 1, c); f(r, c + 1); f(r, c - 1);
            }
          } break;
          default: assert(false);
        }
      }
/*
if((sx==0||sx==M-1)&&(sy==0||sy==N-1)){
 cerr<<STR[k]<<" "<<sx<<" "<<sy<<endl;
 for(int x=0;x<M;++x)pv(d[x],d[x]+N);
 cerr<<endl;
}
*/
      for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
        assert(-1 <= d[x][y]); assert(d[x][y] <= 30);
      }
    }
  }
  
  memset(fs, ~0, sizeof(fs));
  
  vector<int> all(M * N);
  for (int u = 0; u < M * N; ++u) all[u] = u;
  const vector<int> sol{id(0, 0), id(0, 7), id(9, 0), id(9, 7)};
  assert(check(all, sol));
cerr<<"OK!"<<endl;
  
  int P;
  scanf("%d", &P);
  vector<int> S(P);
  for (int p = 0; p < P; ++p) {
    int x, y;
    scanf("%d%d", &x, &y);
    S[p] = id(x, y);
  }
  
  for (int u = 0; u < M * N; ++u) {
    if (solve(S, {u})) return 0;
  }
  for (int u = 0; u < M * N; ++u) for (int v = u + 1; v < M * N; ++v) {
    if (solve(S, {u, v})) return 0;
  }
  for (int u = 0; u < M * N; ++u) for (int v = u + 1; v < M * N; ++v) for (int w = v + 1; w < M * N; ++w) {
    if (solve(S, {u, v, w})) return 0;
  }
  if (solve(S, sol)) return 0;
  assert(false);
  
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 69628kb

input:

1
9 0
8

output:

1
? 1 8
! S

result:

ok number is guessed.

Test #2:

score: 0
Accepted
time: 4ms
memory: 69852kb

input:

4
2 1
2 3
2 5
2 7
5
2

output:

2
? 0 0
? 5 4
! M

result:

ok number is guessed.

Test #3:

score: 0
Accepted
time: 3ms
memory: 69844kb

input:

1
2 4
-1
1

output:

2
? 0 0
? 0 2
! X

result:

ok number is guessed.

Test #4:

score: 0
Accepted
time: 4ms
memory: 69552kb

input:

1
5 0
6

output:

1
? 3 6
! S

result:

ok number is guessed.

Test #5:

score: 0
Accepted
time: 0ms
memory: 69504kb

input:

1
6 0
6

output:

1
? 0 2
! S

result:

ok number is guessed.

Test #6:

score: 0
Accepted
time: 3ms
memory: 69840kb

input:

2
7 7
1 0
-1
6

output:

2
? 0 0
? 7 2
! S

result:

ok number is guessed.

Test #7:

score: 0
Accepted
time: 3ms
memory: 69552kb

input:

5
8 6
1 3
0 5
2 4
0 2
6
3

output:

2
? 0 0
? 8 1
! M

result:

ok number is guessed.

Test #8:

score: 0
Accepted
time: 0ms
memory: 69840kb

input:

6
0 7
1 6
2 8
0 5
7 6
8 2
-1
14

output:

2
? 0 0
? 8 1
! B

result:

ok number is guessed.

Test #9:

score: 0
Accepted
time: 3ms
memory: 69580kb

input:

7
6 5
3 0
3 2
4 1
4 0
2 4
5 2
5
4

output:

2
? 0 0
? 8 7
! M

result:

ok number is guessed.

Test #10:

score: 0
Accepted
time: 0ms
memory: 69612kb

input:

8
3 3
2 5
6 2
7 4
1 4
3 0
2 4
3 4
7
-1

output:

2
? 0 1
? 7 7
! S

result:

ok number is guessed.

Test #11:

score: -100
Runtime Error

input:

9
2 7
2 4
2 5
2 2
2 1
2 0
2 6
2 3
2 8

output:

3
? 0 0

result: