QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#702269 | #9537. Chinese Chess | HoMaMaOvO (Riku Kawasaki, Masaki Nishimoto, Yui Hosaka)# | RE | 4ms | 69852kb | C++14 | 5.5kb | 2024-11-02 15:36:22 | 2024-11-02 15:36:23 |
Judging History
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