QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #149473 | #5509. Kooky Tic-Tac-Toe | Fighoh | WA | 18ms | 3496kb | C++20 | 9.7kb | 2023-08-24 17:46:35 | 2023-08-24 17:46:36 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <queue>
#include <stack>
#include <tuple>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
#define N maxn
#define db double
#define il inline
#define fir first
#define sec second
#define eps (1e-8)
#define pb push_back
#define ll long long
#define mkp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define lowbit(a) (a & (-a))
#define SZ(a) ((int)a.size())
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define split cout << "=========\n";
#define GG { cout << "NO\n"; return; }
#define pll pair<long long, long long>
#define equals(a, b) (fabs((a) - (b)) < eps)
constexpr int ON = 0;
constexpr int CW = -1;
constexpr int CCW = 1;
constexpr int BACK = 2;
constexpr int FRONT = -2;
const db pi = acos(-1.000);
constexpr int maxn = 2e5 + 50;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 998244353; /* 1e9 + 7 */
constexpr int dir[8][2] = {-1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1, 0, -1, -1, -1};
mt19937_64 rnd(random_device {}());
uniform_int_distribution<ull> dist(0, ULLONG_MAX);//use dist(rnd)
bool BEGIN;
void solve() {
int n, k; cin >> n >> k;
vector<string> mp(n);
vector<pii> op1, op2;
int x = 0, y = 0, z = 0;
for (int i = 0; i < n; ++i) {
cin >> mp[i];
for (int j = 0; j < n; ++j) {
if (mp[i][j] == 'x') {
x++;
op1.pb({i + 1, j + 1});
}
if (mp[i][j] == 'o') {
y++;
op2.pb({i + 1, j + 1});
}
if (mp[i][j] == '.') z++;
}
}
auto check = [&](vector<string> &s) -> bool {
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (s[i][j] == '.') continue;
for (int p = 0; p < 8; ++p) {
bool f = 1;
for (int o = 1; o < k; ++o) {
int ni = i + dir[p][0] * o, nj = j + dir[p][1] * o;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
if (s[ni][nj] != s[i][j]) {
f = 0;
break;
}
} else {
f = 0;
break;
}
}
if (f) return 1;
}
}
return 0;
};
bool flag = check(mp);
int posx = -1, posy = -1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (mp[i][j] == '.') continue;
vector<string> np = mp;
for (int p = 0; p < 8; ++p) {
int o;
for (o = 1; o < 10; ++o) {
int ni = i + dir[p][0] * o, nj = j + dir[p][1] * o;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
if (np[ni][nj] != mp[i][j]) {
break;
}
} else {
break;
}
}
if (o >= k) {
np[i][j] = '.';
for (o = 1; o < 10; ++o) {
int ni = i + dir[p][0] * o, nj = j + dir[p][1] * o;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
if (np[ni][nj] != mp[i][j]) {
break;
} else {
np[ni][nj] = '.';
}
} else {
break;
}
}
}
}
if (check(np)) continue;
else {
posx = i, posy = j;
break;
}
}
if (posx != -1) break;
}
// cout << posx << ' ' << posy << '\n';
if (!flag && z) {
cout << "NIE\n";
return ;
}
if (abs(x - y) > 1) {
cout << "NIE\n";
} else {
if (posx != -1 && posy != -1) {
if (!z) {
cout << "TAK\n";
if (x > y) {
for (int i = 0, j = 0; i < SZ(op1) || j < SZ(op2);) {
if (i == j) {
cout << op1[i].fir << ' ' << op1[i].sec << '\n';
i++;
} else {
cout << op2[j].fir << ' ' << op2[j].sec << '\n';
j++;
}
}
} else {
for (int i = 0, j = 0; i < SZ(op1) || j < SZ(op2);) {
if (i != j) {
cout << op1[i].fir << ' ' << op1[i].sec << '\n';
i++;
} else {
cout << op2[j].fir << ' ' << op2[j].sec << '\n';
j++;
}
}
}
} else {
op1.clear(); op2.clear();
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (i == posx && j == posy) continue;
if (mp[i][j] == 'x') op1.pb({i + 1, j + 1});
else if (mp[i][j] == 'o') op2.pb({i + 1, j + 1});
}
if (mp[posx][posy] == 'x') {
posx++; posy++;
if (x < y) {
cout << "NIE\n";
} else {
cout << "TAK\n";
if (x > y) {
for (int i = 0, j = 0; i < SZ(op1) || j < SZ(op2);) {
if (i == j) {
cout << op1[i].fir << ' ' << op1[i].sec << '\n';
i++;
} else {
cout << op2[j].fir << ' ' << op2[j].sec << '\n';
j++;
}
}
cout << posx << ' ' << posy << '\n';
} else {
for (int i = 0, j = 0; i < SZ(op1) || j < SZ(op2);) {
if (i != j) {
cout << op1[i].fir << ' ' << op1[i].sec << '\n';
i++;
} else {
cout << op2[j].fir << ' ' << op2[j].sec << '\n';
j++;
}
}
cout << posx << ' ' << posy << '\n';
}
}
} else {
posx++; posy++;
if (x > y) {
cout << "NIE\n";
} else {
cout << "TAK\n";
if (x < y) {
for (int i = 0, j = 0; i < SZ(op1) || j < SZ(op2);) {
if (i != j) {
cout << op1[i].fir << ' ' << op1[i].sec << '\n';
i++;
} else {
cout << op2[j].fir << ' ' << op2[j].sec << '\n';
j++;
}
}
cout << posx << ' ' << posy << '\n';
} else {
for (int i = 0, j = 0; i < SZ(op1) || j < SZ(op2);) {
if (i == j) {
cout << op1[i].fir << ' ' << op1[i].sec << '\n';
i++;
} else {
cout << op2[j].fir << ' ' << op2[j].sec << '\n';
j++;
}
}
cout << posx << ' ' << posy << '\n';
}
}
}
}
} else if (!flag) {
cout << "TAK\n";
if (x > y) {
for (int i = 0; i < SZ(op2); ++i) {
cout << op1[i].fir << ' ' << op1[i].sec << '\n';
cout << op2[i].fir << ' ' << op2[i].sec << '\n';
}
cout << op1.back().fir << ' ' << op1.back().sec << '\n';
} else {
for (int i = 0; i < SZ(op1); ++i) {
cout << op2[i].fir << ' ' << op2[i].sec << '\n';
cout << op1[i].fir << ' ' << op1[i].sec << '\n';
}
if (y > x) cout << op2.back().fir << ' ' << op2.back().sec << '\n';
}
} else {
cout << "NIE\n";
}
}
}
bool END;
signed main() {
// cout << fixed << setprecision(10);
ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T; while (T--)
solve();
// cout << ((&END - & BEGIN) >> 21) << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3488kb
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: 18ms
memory: 3496kb
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 1 1 2 1 1 2 2 3 1 3 2 4 1 4 3 1 2 2 3 3 ...
result:
wrong answer Contestant's solution makes an incorrect last move (test case 31)