QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#150624#5509. Kooky Tic-Tac-ToeahsoltanWA 14ms3588kbC++172.0kb2023-08-25 22:19:252023-08-25 22:19:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-25 22:19:25]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:3588kb
  • [2023-08-25 22:19:25]
  • 提交

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 ok = true;
    vector<pair<int, int>> x, o;
    vector<pair<int, int>> win;
    bool xw = false;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (g[i][j] == '.') {
          continue;
        }
        (g[i][j] == 'x' ? x : o).push_back({i, j});
        for (int d = 0; d < 4; d++) {
          vector<pair<int, int>> v;
          int p = i;
          int q = j;
          for (int l = 0; l < k; l++) {
            if (p >= n || q >= n || p < 0 || q < 0 || g[p][q] != g[i][j]) {
              break;
            }
            v.push_back({p, q});
            p += DX[d];
            q += DY[d];
          }
          if ((int)v.size() == k) {
            ok &= win.empty();
            win = v;
            xw = g[i][j] == 'x';
          }
        }
      }
    }
    int xs = x.size();
    int os = o.size();
    if (win.empty()) {
      ok &= xs + os == n * n && abs(xs - os) == n % 2;
    } else {
      ok &= xs == os || (abs(xs - os) == 1 && max(xs, os) == (xw ? xs : os));
    }
    if (!ok) {
      cout << "NIE\n";
    } else {
      cout << "TAK\n";
      for (auto p : win) {
        auto& v = xw ? x : o;
        v.erase(find(v.begin(), v.end(), p));
        v.push_back(p);
      }
      int i = 0;
      int j = 0;
      while (i + j < xs + os) {
        pair<int, int> p;
        if (i == j) {
          p = ((xs > os || (xs == os && !xw)) ? x[i++] : o[j++]);
        } else {
          p = (i < j ? x[i++] : o[j++]);
        }
        cout << p.first + 1 << ' ' << p.second + 1 << '\n';
      }
    }
  }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

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 1
3 1
2 2
3 3
2 3
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: -100
Wrong Answer
time: 14ms
memory: 3512kb

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 1
3 1
2 2
3 3
2 3
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 1
3 1
1 2
3 2
1 3
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 1
3 1
4 2
3 2
4 3
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
TAK
1 2
1 1
2 1
3 2
2 2
3 3
...

result:

wrong answer Jury claims solution exists, contestant claims it does not (test case 31)