QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#702571 | #9537. Chinese Chess | ucup-team087# | RE | 0ms | 0kb | C++14 | 5.3kb | 2024-11-02 16:13:28 | 2024-11-02 16:13:29 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
1 9 0
output:
0 1 ? 1 8