QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#150723#5509. Kooky Tic-Tac-ToeahsoltanAC ✓72ms3756kbC++172.2kb2023-08-26 01:56:252023-08-26 01:56:28

Judging History

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

  • [2023-08-26 01:56:28]
  • 评测
  • 测评结果:AC
  • 用时:72ms
  • 内存:3756kb
  • [2023-08-26 01:56: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 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)