QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#377585 | #5509. Kooky Tic-Tac-Toe | ckiseki# | WA | 5ms | 3672kb | C++20 | 5.6kb | 2024-04-05 15:38:02 | 2024-04-05 15:38:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
void solve() {
int n, k;
cin >> n >> k;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
vector<tuple<char,int,int>> final_pos;
for (char c : "ox") {
vector<pair<int,int>> vs;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
vs.emplace_back(i, j);
int c_has_win = 0;
for (int x = 0; x < n; x++) {
for (int i = 0; i + k <= n; i++) {
bool ok = true;
for (int j = 0; j < k; j++) ok &= s[x][i + j] == c;
if (!ok) continue;
vector<pair<int,int>> v, tmp;
for (int j = 0; j < k; j++) v.emplace_back(x, i + j);
assert(is_sorted(all(v)));
set_intersection(all(vs), all(v), back_inserter(tmp));
vs = tmp;
c_has_win += 1;
}
}
for (int x = 0; x < n; x++) {
for (int i = 0; i + k <= n; i++) {
bool ok = true;
for (int j = 0; j < k; j++) ok &= s[i + j][x] == c;
if (!ok) continue;
vector<pair<int,int>> v, tmp;
for (int j = 0; j < k; j++) v.emplace_back(i + j, x);
assert(is_sorted(all(v)));
set_intersection(all(vs), all(v), back_inserter(tmp));
vs = tmp;
c_has_win += 1;
}
}
for (int x = 0; x + k <= n; x++) {
for (int y = 0; y + k <= n; y++) {
bool ok = true;
for (int j = 0; j < k; j++) ok &= s[x + j][y + j] == c;
if (!ok) continue;
vector<pair<int,int>> v, tmp;
for (int j = 0; j < k; j++) v.emplace_back(x + j, y + j);
assert(is_sorted(all(v)));
set_intersection(all(vs), all(v), back_inserter(tmp));
vs = tmp;
c_has_win += 1;
}
}
for (int x = 0; x + k <= n; x++) {
for (int y = k - 1; y < n; y++) {
bool ok = true;
for (int j = 0; j < k; j++) ok &= s[x + j][y - j] == c;
if (!ok) continue;
vector<pair<int,int>> v, tmp;
for (int j = 0; j < k; j++) v.emplace_back(x + j, y - j);
assert(is_sorted(all(v)));
set_intersection(all(vs), all(v), back_inserter(tmp));
vs = tmp;
c_has_win += 1;
}
}
// debug(vs.size());
// for (auto [x, y] : vs) debug(x, y);
// debug(c_has_win);
if (c_has_win > 0) {
if (c_has_win > 1) {
if (vs.size() != 1) {
cout << "NIE\n";
return;
}
assert(vs.size() == 1);
auto [x, y] = vs[0];
final_pos.emplace_back(c, x, y);
} else {
assert(vs.size() == k);
auto [x, y] = vs[0];
final_pos.emplace_back(c, x, y);
}
} else {
assert(vs.size() == n * n);
}
}
int cnto = 0, cntx = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (s[i][j] == 'o') {
++cnto;
} else if (s[i][j] == 'x') {
++cntx;
}
}
if (final_pos.empty()) {
if (cnto + cntx != n * n) {
cout << "NIE\n";
return;
}
char first_c;
if (cnto == cntx + 1) {
first_c = 'o';
} else if (cntx == cnto + 1) {
first_c = 'x';
} else if (cntx == cnto) {
first_c = 'o';
} else {
cout << "NIE\n";
return;
}
vector<pair<int,int>> p1, p2;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (s[i][j] == first_c)
p1.emplace_back(i, j);
else if (s[i][j] == ('o' ^ 'x' ^ first_c))
p2.emplace_back(i, j);
}
assert(p1.size() + p2.size() == cntx + cnto);
cout << "TAK\n";
for (int i = 0; i < cntx + cnto; i++) {
int x, y;
if (~i & 1)
tie(x, y) = p1[i >> 1];
else
tie(x, y) = p2[i >> 1];
cout << x + 1 << ' ' << y + 1 << '\n';
}
return;
}
if (final_pos.size() != 1) {
cout << "NIE\n";
return;
}
auto [final_c, final_x, final_y] = final_pos[0];
char first_c;
if (cnto == cntx + 1) {
first_c = 'o';
if (final_c == 'x') {
cout << "NIE\n";
return;
}
} else if (cntx == cnto + 1) {
first_c = 'x';
if (final_c == 'o') {
cout << "NIE\n";
return;
}
} else if (cntx == cnto) {
first_c = 'x' ^ 'o' ^ final_c;
} else {
cout << "NIE\n";
return;
}
s[final_x][final_y] = '#';
vector<pair<int,int>> p1, p2;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (s[i][j] == first_c)
p1.emplace_back(i, j);
else if (s[i][j] == ('o' ^ 'x' ^ first_c))
p2.emplace_back(i, j);
}
if (final_c == first_c)
p1.emplace_back(final_x, final_y);
else
p2.emplace_back(final_x, final_y);
debug(first_c, char('o'^'x'^first_c));
assert(p1.size() + p2.size() == cntx + cnto);
cout << "TAK\n";
for (int i = 0; i < cntx + cnto; i++) {
int x, y;
if (~i & 1)
tie(x, y) = p1[i >> 1];
else
tie(x, y) = p2[i >> 1];
cout << x + 1 << ' ' << y + 1 << '\n';
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
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: 5ms
memory: 3672kb
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 exists, contestant claims it does not (test case 3522)