QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#377614 | #5509. Kooky Tic-Tac-Toe | 8BQube# | WA | 10ms | 3604kb | C++20 | 3.7kb | 2024-04-05 15:58:29 | 2024-04-05 15:58:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()
struct S {
int res, x, y, dx, dy; // -1, 0, 1
};
void solve() {
int n, k;
cin >> n >> k;
vector<vector<int>> v(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < n; j++)
if (s[j] == 'o')
v[i][j] = 1;
else if (s[j] == 'x')
v[i][j] = -1;
}
int any = false;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (v[i][j] == 0)
any = true;
auto in = [&](int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
};
auto chk_win_single = [&](int dx, int dy) -> S {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (v[i][j] != 0 && in(i + (k - 1) * dx, j + (k - 1) * dy)) {
bool ok = true;
int x = i, y = j;
for (int t = 1; t < k; t++) {
x += dx, y += dy;
if (v[i][j] != v[x][y]) {
ok = false;
break;
}
}
if (ok)
return {v[i][j], i, j, dx, dy};
}
return {0, -1, -1, -1, -1};
};
auto chk_win = [&]() -> S {
const vector<pii> opt = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
for (auto [dx, dy] : opt) {
auto s = chk_win_single(dx, dy);
if (s.res)
return s;
}
return {0, -1, -1, -1, -1};
};
auto can_play = [&](int x) {
int y = x * -1;
int cx = 0, cy = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (v[i][j] == x)
cx++;
else if (v[i][j] == y)
cy++;
if (cx == cy)
return x;
else if (cx == cy + 1)
return y;
else
return 0;
};
auto play = [&](int x) {
cout << "TAK" << "\n";
int y = x * -1;
queue<pii> vx, vy;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (v[i][j] == x)
vx.push({i, j});
else if (v[i][j] == y)
vy.push({i, j});
for (int now = x, nxt = y; ; swap(now, nxt)) {
auto &q = (now == x ? vx : vy);
if (!SZ(q))
break;
cout << q.front().X + 1 << " " << q.front().Y + 1 << "\n";
q.pop();
}
};
auto p = chk_win();
if (!p.res) {
if (any)
cout << "NIE\n";
else if (can_play(1))
play(1);
else if (can_play(-1))
play(-1);
else
cout << "NIE\n";
return;
}
for (int i = 0; i < k; i++) {
int x = p.x + i * p.dx;
int y = p.y + i * p.dy;
v[x][y] = 0;
if (chk_win().res == 0) {
if (can_play(1) == p.res) {
play(1);
cout << x + 1 << " " << y + 1 << "\n";
}
else if (can_play(-1)) {
play(-1);
cout << x + 1 << " " << y + 1 << "\n";
}
else
cout << "NIE\n";
return;
}
v[x][y] = p.res;
}
cout << "NIE\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int T;
cin >> T;
while (T--)
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
7 3 3 x.o xxx o.o 4 3 xx.x ...o ..o. .o.. 3 3 xoo oxx xoo 3 2 xoo oxx xoo 3 3 xox .o. xox 3 2 xo. ..x xo. 3 3 x.. .x. ..x
output:
TAK 1 1 1 3 2 2 3 1 2 3 3 3 2 1 TAK 1 1 3 3 1 2 4 2 1 4 2 4 TAK 1 2 1 1 1 3 2 2 2 1 2 3 3 2 3 1 3 3 NIE NIE NIE NIE
result:
ok correct (7 test cases)
Test #2:
score: -100
Wrong Answer
time: 10ms
memory: 3552kb
input:
10000 3 3 x.o xxx o.o 3 3 xoo oxx xoo 3 2 xoo oxx xoo 3 3 xox .o. xox 3 2 xo. ..x xo. 3 2 oox .xo o.x 5 5 xxx.. xxo.x xoo.. xxxox .oooo 3 3 xxx .o. oo. 3 2 x.o xo. ..o 3 2 ..x xxo .o. 3 3 xxo o.. oxo 3 2 oox ..x ... 3 3 xxo ... .ox 3 3 .xo ... oox 3 3 .x. xo. o.o 3 2 o.. xxo .ox 3 2 x.x xoo x.o 3 2 ...
output:
TAK 1 1 1 3 2 2 3 1 2 3 3 3 2 1 TAK 1 2 1 1 1 3 2 2 2 1 2 3 3 2 3 1 3 3 NIE NIE NIE NIE NIE TAK 2 2 1 2 3 1 1 3 3 2 1 1 NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK 1 2 1 1 1 3 1 4 2 3 2 2 2 4 4 2 3 1 4 3 3 2 4 1 NIE NIE NIE NIE NIE TAK 2 1 1 1 2 3 1 3 2 4 1 4 3 1 2 2 3 3 3 2 ...
result:
wrong answer Jury claims solution does not exist, contestant claims it does (test case 1126)