QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#344148#5509. Kooky Tic-Tac-Toeucup-team1198#WA 14ms3572kbC++204.3kb2024-03-03 17:04:342024-03-03 17:04:35

Judging History

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

  • [2024-03-03 17:04:35]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:3572kb
  • [2024-03-03 17:04:34]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<string> tab(n);
    for (int i = 0; i < n; ++i) {
        cin >> tab[i];
    }

    vector<pair<int, int>> posx;
    vector<pair<int, int>> poso;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (tab[i][j] == 'x') posx.push_back({i, j});
            if (tab[i][j] == 'o') poso.push_back({i, j});
        }
    }

    vector<int> dx = {-1, 0, 1, 1};
    vector<int> dy = {1, 1, 1, 0};

    auto check = [&](int i, int j) {
        return 0 <= i && i < n && 0 <= j && j < n;
    };

    auto get_win = [&](char who, pair<int, int>& where) {
        vector<vector<int>> cntt(n, vector<int>(n, 0));
        int cnt = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int d = 0; d < 4; ++d) {
                    bool good = true;
                    for (int t = 0; t < k; ++t) {
                        int i1 = i + dx[d] * t;
                        int j1 = j + dy[d] * t;
                        if (!check(i1, j1) || tab[i1][j1] != who) {
                            good = false;
                            break;
                        }
                    }

                    if (good) {
                        cnt++;
                        for (int t = 0; t < k; ++t) {
                            int i1 = i + dx[d] * t;
                            int j1 = j + dy[d] * t;
                            cntt[i1][j1]++;
                        }

                    }
                }
            }
        }

        if (cnt == 0) {
            where = {-2, -2};
            return;
        }

        where = {-1, -1};
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (cntt[i][j] == cnt) {
                    where = {i, j};
                }
            }
        }
    };

    auto play = [](vector<pair<int, int>> p1, vector<pair<int, int>> p2) {
        if (p1.size() != p2.size() && p1.size() != p2.size() + 1) {
            cout << "NIE\n";
            return;
        } else {
            cout << "TAK\n";
            for (int i = 0; i < p1.size(); ++i) {
                cout << p1[i].first + 1 << ' ' << p1[i].second + 1 << '\n';
                if (i < p2.size()) {
                    cout << p2[i].first + 1 << ' ' << p2[i].second + 1 << '\n';
                }
            }
            return;
        }
    };

    pair<int, int> wx;
    get_win('x', wx);

    pair<int, int> wo;
    get_win('o', wo);

    if (wx.first == -2 && wo.first == -2) {
        if (poso.size() + posx.size() == n * n) {
            if (poso.size() > posx.size()) {
                play(poso, posx);
            } else {
                play(posx, poso);
            }
            return;
        } else {
            cout << "NIE\n";
            return;            
        }

    }
    if (wx.first != -2 && wo.first != -2) {
        cout << "NIE\n";
        return;
    }
    if (wx.first == -1 || wo.first == -1) {
        cout << "NIE\n";
        return;
    }

    if (wo.first == -2) {
        // wins x;
        auto it = find(posx.begin(), posx.end(), wx);
        swap(*it, posx.back());

        if (posx.size() > poso.size()) {
            play(posx, poso);
        } else if (poso.size() == poso.size()) {
            play(poso, posx);
        } else {
            cout << "NIE\n";
            return;
        }
    }

    if (wx.first == -2) {
        // wins 0;
        auto it = find(poso.begin(), poso.end(), wo);
        swap(*it, poso.back());

        if (poso.size() > posx.size()) {
            play(poso, posx);
        } else if (poso.size() == posx.size()) {
            play(posx, poso);
        } else {
            cout << "NIE\n";
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

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

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3548kb

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
2 4
1 2
3 3
1 4
4 2
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: 3572kb

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

result:

wrong answer Jury claims solution does not exist, contestant claims it does (test case 63)