QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#702571#9537. Chinese Chessucup-team087#RE 0ms0kbC++145.3kb2024-11-02 16:13:282024-11-02 16:13:29

Judging History

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

  • [2024-11-02 16:13:29]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-02 16:13:28]
  • 提交

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];

using Cand = pair<int, pair<int, int>>;
int check(int q, const vector<Cand> &cands) {
  if (!cands.size()) return -2;
  {
    const int k0 = cands[0].first;
    bool same = true;
    for (const auto &c : cands) same = same && (k0 == c.first);
    if (same) return -2;
  }
  if (q == 0) return -1;
  for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
    vector<Cand> css[32];
    for (const auto &c : cands) {
      const int d = dist[c.first][c.second.first][c.second.second][x][y];
      css[1 + d].push_back(c);
    }
    bool ok = true;
    for (int d = -1; d <= 30; ++d) {
      if (!~check(q - 1, css[1 + d])) {
        ok = false;
        break;
      }
    }
    if (ok) {
      return id(x, y);
    }
  }
  return -1;
}

void solve(int q, const vector<Cand> &cands) {
// cerr<<"[solve] "<<q<<" "<<cands<<endl;
  const int res = check(q, cands);
  assert(~res);
  if (res == -2) {
    assert(cands.size());
    const int k0 = cands[0].first;
    printf("! %c\n", STR[k0]); fflush(stdout);
    return;
  }
  const int x = res / N, y = res % N;
  printf("? %d %d\n", x, y); fflush(stdout);
  int D;
  scanf("%d", &D);
  vector<Cand> cs;
  for (const auto &c : cands) {
    if (D == dist[c.first][c.second.first][c.second.second][x][y]) {
      cs.push_back(c);
    }
  }
  solve(q - 1, cs);
}

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);
      }
    }
  }
  
  vector<Cand> all;
  for (int k = 0; k < K; ++k) for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
    all.emplace_back(k, make_pair(x, y));
  }
  const int res = check(3, all);
  assert(~res);
cerr<<"OK! "<<res<<endl;
  
  int P;
  scanf("%d", &P);
  vector<int> X(P), Y(P);
  for (int p = 0; p < P; ++p) {
    scanf("%d%d", &X[p], &Y[p]);
  }
  vector<Cand> cands;
  for (int k = 0; k < K; ++k) for (int p = 0; p < P; ++p) {
    cands.emplace_back(k, make_pair(X[p], Y[p]));
  }
  for (int q = 0; ; ++q) {
    printf("%d\n", q); fflush(stdout);
    if (~check(q, cands)) {
      solve(q, cands);
      break;
    }
  }
  return 0;
}

详细

Test #1:

score: 0
Runtime Error

input:

1
9 0

output:

0
1
? 1 8

result: