QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377585#5509. Kooky Tic-Tac-Toeckiseki#WA 5ms3672kbC++205.6kb2024-04-05 15:38:022024-04-05 15:38:03

Judging History

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

  • [2024-04-05 15:38:03]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3672kb
  • [2024-04-05 15:38:02]
  • 提交

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)