QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377614#5509. Kooky Tic-Tac-Toe8BQube#WA 10ms3604kbC++203.7kb2024-04-05 15:58:292024-04-05 15:58:30

Judging History

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

  • [2024-04-05 15:58:30]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3604kb
  • [2024-04-05 15:58:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

struct S {
    int res, x, y, dx, dy; // -1, 0, 1
};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> v(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++)
            if (s[j] == 'o')
                v[i][j] = 1;
            else if (s[j] == 'x')
                v[i][j] = -1;
    }
    int any = false;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (v[i][j] == 0)
                any = true;
    auto in = [&](int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    };
    auto chk_win_single = [&](int dx, int dy) -> S {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (v[i][j] != 0 && in(i + (k - 1) * dx, j + (k - 1) * dy)) {
                    bool ok = true;
                    int x = i, y = j;
                    for (int t = 1; t < k; t++) {
                        x += dx, y += dy;
                        if (v[i][j] != v[x][y]) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok)
                        return {v[i][j], i, j, dx, dy};
                }
        return {0, -1, -1, -1, -1};
    };
    auto chk_win = [&]() -> S {
        const vector<pii> opt = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
        for (auto [dx, dy] : opt) {
            auto s = chk_win_single(dx, dy);
            if (s.res)
                return s;
        }
        return {0, -1, -1, -1, -1};
    };
    auto can_play = [&](int x) { 
        int y = x * -1; 
        int cx = 0, cy = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (v[i][j] == x)
                    cx++;
                else if (v[i][j] == y)
                    cy++;
        if (cx == cy)
            return x;
        else if (cx == cy + 1)
            return y;
        else
            return 0;
    };
    auto play = [&](int x) {
        cout << "TAK" << "\n";
        int y = x * -1; 
        queue<pii> vx, vy;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (v[i][j] == x)
                    vx.push({i, j});
                else if (v[i][j] == y)
                    vy.push({i, j});
        for (int now = x, nxt = y; ; swap(now, nxt)) {
            auto &q = (now == x ? vx : vy);
            if (!SZ(q))
                break;
            cout << q.front().X + 1 << " " << q.front().Y + 1 << "\n";
            q.pop();
        }
    };
    auto p = chk_win();
    if (!p.res) {
        if (any)
            cout << "NIE\n";
        else if (can_play(1))
            play(1);
        else if (can_play(-1))
            play(-1);
        else
            cout << "NIE\n";
        return;
    }
    for (int i = 0; i < k; i++) {
        int x = p.x + i * p.dx;
        int y = p.y + i * p.dy;
        v[x][y] = 0;
        if (chk_win().res == 0) {
            if (can_play(1) == p.res) {
                play(1);
                cout << x + 1 << " " << y + 1 << "\n";
            }
            else if (can_play(-1)) {
                play(-1);
                cout << x + 1 << " " << y + 1 << "\n";
            }
            else
                cout << "NIE\n";
            return;
        }
        v[x][y] = p.res;
    }
    cout << "NIE\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
}

詳細信息

Test #1:

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

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: 10ms
memory: 3552kb

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 does not exist, contestant claims it does (test case 1126)