QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#221855#5509. Kooky Tic-Tac-Toeucup-team859#WA 19ms3692kbC++233.8kb2023-10-21 14:51:242023-10-21 14:51:26

Judging History

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

  • [2023-10-21 14:51:26]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:3692kb
  • [2023-10-21 14:51:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

using ll = long long;
using ull = unsigned long long;

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(const pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename T>
string to_string(const T &v) {
  string s = "{";
  bool first = true;
  for (const auto &it : v) {
    if (!first)
      s += ", ";
    else
      first = false;
    s += to_string(it);
  }
  return s += "}";
}

void debug_out() {
  cerr << endl;
}

template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
  cerr << to_string(first) << " ";
  debug_out(rest...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

auto startTime = high_resolution_clock::now();
int get_time() {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  return duration.count(); // in ms
}

void solve() {
  int n, m, k;
  cin >> n >> k;
  m = n;

  vector<string> s(n);
  for (int i = 0; i < n; ++i)
    cin >> s[i];

  int nx = 0, no = 0, lib = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (s[i][j] == 'x')
        ++nx;
      else if (s[i][j] == 'o')
        ++no;
      else
        ++lib;
    }
  }

  auto check_win = [&]() {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (s[i][j] == '.')
          continue;

        bool ok = true;
        for (int t = 1; t < k; ++t) {
          if (!(j + t < n && s[i][j] == s[i][j + t]))
            ok = false;
        }
        if (ok)
          return true;

        ok = true;
        for (int t = 1; t < k; ++t) {
          if (!(i + t < n && s[i][j] == s[i + t][j]))
            ok = false;
        
        }
        if (ok)
          return true;
        
        ok = true;
        for (int t = 1; t < k; ++t) {
          if (!(j + t < n && i + t < n && s[i][j] == s[i + t][j + t]))
            ok = false;
        }
        if (ok)
          return true;
        
        ok = true;
        for (int t = 1; t < k; ++t) {
          if (!(j - t >= 0 && i + t < n && s[i][j] == s[i + t][j - t]))
            ok = false;
        }
        if (ok)
          return true;
      }
    }

    return false;
  };

  if (no > nx) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (s[i][j] == 'o')
          s[i][j] = 'x';
        else if (s[i][j] == 'x')
          s[i][j] = 'o';
      }
    }
    swap(no, nx);
  }

  if (no + 1 < nx || (!check_win() && lib > 0)) {
    cout << "NIE\n";
    return;
  }

  vector<pair<int, int>> ans;
  while (no > 0 || nx > 0) {
    char ch = 'x';
    bool found = false;
    if (no == nx)
      ch = 'o';

    for (int i = 0; i < n && !found; ++i) {
      for (int j = 0; j < m; ++j) {
        if (s[i][j] == ch) {
          s[i][j] = '.';
          if (!check_win()) {
            found = true;
            ans.push_back({i, j});
            break;
          }
          s[i][j] = ch;
        }
      }
    }

    if (!found) {
      cout << "NIE\n";
      return;
    }

    if (no == nx)
      --no;
    else
      --nx;
  }

  cout << "TAK\n";
  reverse(ans.begin(), ans.end());
  for (auto it : ans)
    cout << it.first + 1 << " " << it.second + 1 << endl;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int t = 1;
  cin >> t;
  while (t--)
    solve();

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

result:

ok correct (7 test cases)

Test #2:

score: -100
Wrong Answer
time: 19ms
memory: 3564kb

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

result:

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