QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#607857#5509. Kooky Tic-Tac-Toehzy99999#WA 1ms3640kbC++206.9kb2024-10-03 16:46:192024-10-03 16:46:20

Judging History

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

  • [2024-10-03 16:46:20]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3640kb
查看
  • [2024-10-03 16:46:19]
  • 提交

answer

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int T;
int n, k;
string s[10];
int a[10][10];
int check(int sx, int sy, int ex, int ey){//k
    bool flagx = 1, flago = 1;
    if(sx == ex) {
        for (int i = sy; i <= ey; i++) {
            flagx &= (s[sx][i] == 'x');
            flago &= (s[sx][i] == 'o');
        }
        if (flagx)return 1;
        else if (flago)return -1;
    }
    else if (sy == ey) {
        for (int i = sx; i <= ex; i++) {
            flagx &= (s[i][sy] == 'x');
            flago &= (s[i][sy] == 'o');
        }
        if (flagx)return 1;
        else if (flago)return -1;
    }
    else {
        int dx = 0, dy = 0;
        if (sx < ex)dx = 1;
        else dx = -1;
        if (sy < ey)dy = 1;
        else dy = -1;
        for (int x = sx, y = sy; x != ex; x += dx, y += dy) {
            flagx &= (s[x][y] == 'x');
            flago &= (s[x][y] == 'o');
        }
        flagx &= (s[ex][ey] == 'x');
        flago &= (s[ex][ey] == 'o');
        if (flagx)return 1;
        else if (flago)return -1;
    }
    return 0;
}
int win() {
    int winx = 0, wino = 0;
    for (int i = 1; i <= n; i++) {
        int sumx = 0, sumo = 0;
        for (int j = 1; j + k - 1 <= n; j++) {
            int t = check(i, j, i, j + k - 1);
            if (t == 1)winx++;
            else if (t == -1)wino++;
        }
    }
    for (int j = 1; j <= n; j++) {
        int sumx = 0, sumo = 0;
        for (int i = 1; i + k - 1 <= n; i++) {
            int t = check(i, j, i + k - 1, j);
            if (t == 1)winx++;
            else if (t == -1)wino++;
        }
    }
    int dx[4] = { 1,1,-1,-1 };
    int dy[4] = { 1,-1,1,-1 };
    PII t;
    int uu = 0, vv = 0;
    for (t.x = 1; t.x <= n; t.x++) {
        for (t.y = 1; t.y <= n; t.y++) {
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] * (k - 1) + t.x;
                int ny = dy[i] * (k - 1) + t.y;
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
                    int tt = check(t.x, t.y, nx, ny);
                    if (tt == 1)uu++;
                    else if (tt == -1)vv++;
                }
            }
        }
    }
    winx += uu / 2;
    wino += vv / 2;
    //cout << "winx" << winx << " " << "winy" << wino << '\n';
    if (winx && wino)return -2;
    else if (winx + wino == 1) {
        if (winx)return 1;
        else return -1;
    }
    return 0;
}
int find(PII t) {
    int dx[8] = { 1,1,1,0,0,-1,-1,-1 };
    int dy[8] = { 1,0,-1,1,-1,1,0,-1 };
    for (int i = 0; i < 8; i++) {
        int nx = dx[i] * (k - 1) + t.x;
        int ny = dy[i] * (k - 1) + t.y;
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
            if (check(t.x, t.y, nx, ny))
                return 1;
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--){
        cin >> n >> k;
        vector<PII>X, O;
        for (int i = 1; i <= n; i++) {
            cin >> s[i];
            s[i] = " " + s[i];
            for (int j = 1; j <= n; j++) {
                a[i][j] = -1;
                if (s[i][j] == 'x')X.push_back({ i,j });
                if (s[i][j] == 'o')O.push_back({ i,j });
            }
        }
        int winner = win();
        if (abs((int)(X.size() - O.size())) > 1) {
            cout << "NIE\n";
            continue;
        }
        else if ((X.size() + O.size()) != n * n && !winner) {
            cout << "NIE\n";
            continue;
        }
        else if (abs(winner) > 1) {
            cout << "NIE\n";
            continue;
        }
        vector<PII>ans;
        if (X.size() >  O.size()) {
            if (winner == -1) {
                cout << "NIE" << '\n';
                continue;
            }
            else if (winner == 0) {
                for (int i = 0; i < O.size(); i++) {
                    ans.push_back(X[i]);
                    ans.push_back(O[i]);
                }
                ans.push_back(X[O.size()]);
            }
            else {
                for (int i = 0; i < X.size(); i++) {
                    if (find(X[i])) {
                        auto t = X[i];
                        X.erase(X.begin() + i);
                        X.push_back(t);
                    }
                }
                for (int i = 0; i < O.size(); i++) {
                    ans.push_back(X[i]);
                    ans.push_back(O[i]);
                }
                ans.push_back(X[O.size()]);
            }
        }else if (X.size() == O.size()) {
            if (winner == 0) {
                for (int i = 0; i < O.size(); i++) {
                    ans.push_back(X[i]);
                    ans.push_back(O[i]);
                }
            }
            else if (winner == 1) {
                for (int i = 0; i < X.size(); i++) {
                    if (find(X[i])) {
                        auto t = X[i];
                        X.erase(X.begin() + i);
                        X.push_back(t);
                    }
                }
                for (int i = 0; i < O.size(); i++) {
                    ans.push_back(O[i]);
                    ans.push_back(X[i]);
                }
            }
            else {
                for (int i = 0; i < O.size(); i++) {
                    if (find(O[i])) {
                        auto t = O[i];
                        O.erase(O.begin() + i);
                        O.push_back(t);
                    }
                }
                for (int i = 0; i < O.size(); i++) {
                    ans.push_back(X[i]);
                    ans.push_back(O[i]);
                }
            }
        }
        else {// X<0
            if (winner == 1) {
                cout << "NIE" << '\n';
                continue;
            }
            else if (winner == 0) {
                for (int i = 0; i < X.size(); i++) {
                    ans.push_back(X[i]);
                    ans.push_back(O[i]);
                }
                ans.push_back(O[X.size()]);
            }
            else {
                for (int i = 0; i < O.size(); i++) {
                    if (find(O[i])) {
                        auto t = O[i];
                        O.erase(O.begin() + i);
                        O.push_back(t);
                    }
                }
                for (int i = 0; i < X.size(); i++) {
                    ans.push_back(O[i]);
                    ans.push_back(X[i]);
                }
                ans.push_back(O[X.size()]);
            }
        }
        cout << "TAK\n";
        for (auto t : ans) {
            cout << t.x << " " << t.y << '\n';
        }
    }
    return 0;
}
/*

*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3640kb

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

result:

wrong answer Contestant's solution doesn't alternate between circles and crosses (test case 3)
English 繁體中文 简体中文

Server Time: 2024-12-05 06:23:49 | OpenSource Project