QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#150723 | #5509. Kooky Tic-Tac-Toe | ahsoltan | AC ✓ | 72ms | 3756kb | C++17 | 2.2kb | 2023-08-26 01:56:25 | 2023-08-26 01:56:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 2137
#endif
const int DX[4] = {1, 0, 1, 1};
const int DY[4] = {-1, 1, 1, 0};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector<string> g(n);
for (int i = 0; i < n; i++) {
cin >> g[i];
}
bool ans = true;
vector<pair<int, int>> pos[2];
vector<vector<pair<int, int>>> win;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] != '.') {
pos[g[i][j] == 'x'].push_back({i, j});
for (int d = 0; d < 4; d++) {
int p = i;
int q = j;
vector<pair<int, int>> w;
for (int l = 0; l < k; l++) {
if (p >= 0 && p < n && q >= 0 && q < n && g[p][q] == g[i][j]) {
w.push_back({p, q});
p += DX[d];
q += DY[d];
}
}
if ((int)w.size() == k) {
win.push_back(w);
}
}
}
}
}
int s[2] = {(int)pos[0].size(), (int)pos[1].size()};
ans &= abs(s[0] - s[1]) <= 1;
int w = -1;
if (!win.empty()) {
w = g[win[0][0].first][win[0][0].second] == 'x';
ans &= s[w] >= s[w ^ 1];
map<pair<int, int>, int> m;
for (auto& v : win) {
for (auto [x, y] : v) {
ans &= (g[x][y] == 'x') == w;
m[{x, y}]++;
}
}
pair<int, int> mx = win[0][0];
for (auto [p, q] : m) {
if (q > m[mx]) {
mx = p;
}
}
ans &= m[mx] == (int)win.size();
for (auto& x : pos[w]) {
if (x == mx) {
swap(x, pos[w].back());
}
}
} else {
ans &= s[0] + s[1] == n * n;
}
if (ans) {
cout << "TAK\n";
int j = w == -1 ? (s[0] > s[1] ? 0 : 1) : (s[0] == s[1] ? w ^ 1 : w);
for (int i = 0; i < s[0] + s[1]; i++) {
cout << pos[j][i / 2].first + 1 << ' ' << pos[j][i / 2].second + 1 << '\n';
j ^= 1;
}
} else {
cout << "NIE\n";
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
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 3 3 1 2 2 3 3 2 1 TAK 1 1 4 2 1 2 3 3 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: 0
Accepted
time: 14ms
memory: 3588kb
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 3 3 1 2 2 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 3 3 1 1 2 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 3 3 1 4 2 3 2 4 1 NIE NIE NIE NIE NIE TAK 2 1 1 1 2 3 4 3 2 4 1 3 3 1 1 4 3 3 2 2 ...
result:
ok correct (10000 test cases)
Test #3:
score: 0
Accepted
time: 72ms
memory: 3756kb
input:
10000 6 4 x.xx.o xo.o.x ooox.o o..xo. ..xxxo o.oxx. 6 5 oooxxx oxoxxo xoooxo xoxxxx xooxox xoxxxx 6 3 o.x.x. oo.o.x xx.oo. .x.xx. ooxo.. .xxo.. 6 6 xoo..o o.xx.x oooooo xx.x.. o..xx. ...xxx 6 5 xooxoo ooxxoo xxooxx oxooxx oxoxxx xxoxoo 6 5 xoxxxo ooooxo ooxoxx oxxoox xxxxox ooooxo 6 5 o....o .ox.oo ...
output:
TAK 1 6 1 1 2 2 1 3 2 4 1 4 3 1 2 1 3 2 2 6 3 3 6 5 3 6 4 4 4 1 5 3 4 5 5 4 5 6 5 5 6 1 6 4 6 3 3 4 NIE TAK 1 3 1 1 1 5 2 1 2 6 2 2 3 1 2 4 3 2 3 4 4 2 3 5 4 4 5 1 4 5 5 2 6 3 5 4 6 2 6 4 5 3 NIE TAK 1 1 1 2 1 4 1 3 2 3 1 5 2 4 1 6 3 1 2 1 3 2 2 2 3 5 2 5 3 6 2 6 4 2 3 3 4 5 3 4 4 6 4 1 5 2 4 3 5 4 ...
result:
ok correct (10000 test cases)