QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#105447#5509. Kooky Tic-Tac-ToeEl_MedonhoAC ✓23ms3456kbC++147.3kb2023-05-14 04:25:502023-05-14 04:25:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-14 04:25:53]
  • 评测
  • 测评结果：AC
  • 用时：23ms
  • 内存：3456kb
查看
  • [2023-05-14 04:25:50]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

#define mxn 1e5+5
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define endl '\n'
#define pii pair<int,int>
typedef long long ll;


int solve(){

    int n,k; cin >> n >> k;

    vector<string> gg(n);
    vector<vector<char>> grid(n, vector<char> (n));

    for(string &s: gg) cin >> s;
    int cc1 = 0,cc2 = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            grid[i][j] = gg[i][j];
            if(grid[i][j] == 'x') cc1++;
            else if(grid[i][j] == 'o') cc2++;
        }
    }

    if(abs(cc1-cc2) > 1){
        cout << "NIE\n";
        return 0;
    }

    pii a1 = {-1,-1}, a2 = {-1,-1};    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // bool pj = false;
            if(i + k <= n){
                bool pass = true;
                for(int g = 0; g < k; g++){
                    if(grid[i+g][j] != 'x') pass = false;
                }
                if(pass) a1 = {i,j};
            }

            if(j + k <= n){
                bool pass = true;
                for(int g = 0; g < k; g++){
                    if(grid[i][j+g] != 'x') pass = false;
                }
                if(pass) a1 = {i,j};
            }

            if(i + k <= n && j + k <= n){
                bool pass = true;
                for(int g = 0; g < k; g++){
                    if(grid[i+g][j+g] != 'x') pass = false;
                }
                if(pass) a1 = {i,j};
            }

            if(i + k <= n && j - k >= -1){
                bool pass = true;
                for(int g = 0; g < k; g++){
                    if(grid[i+g][j-g] != 'x') pass = false;
                }
                if(pass) a1 = {i,j};
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // bool pj = false;
            if(i + k <= n){
                bool pass = true;
                for(int g = 0; g < k; g++){
                    if(grid[i+g][j] != 'o') pass = false;
                }
                if(pass) a2 = {i,j};
            }

            if(j + k <= n){
                bool pass = true;
                for(int g = 0; g < k; g++){
                    if(grid[i][j+g] != 'o') pass = false;
                }
                if(pass) a2 = {i,j};
            }

            if(i + k <= n && j + k <= n){
                bool pass = true;
                for(int g = 0; g < k; g++){
                    if(grid[i+g][j+g] != 'o') pass = false;
                }
                if(pass) a2 = {i,j};
            }

            if(i + k <= n && j - k >= -1){
                bool pass = true;
                for(int g = 0; g < k; g++){
                    if(grid[i+g][j-g] != 'o') pass = false;
                }
                if(pass) a2 = {i,j};
            }
        }
    }

    if((a1.first != -1 && a2.first != -1) || (a1.first == -1 && a2.first == -1 && cc1+cc2 != n*n) ){
        cout << "NIE\n";
        return 0;
    }

    if(a1.first == -1 && a2.first == -1){
        cout << "TAK\n";

        bool cross = (cc2 > cc1) ? false : true;
        bool doo = true;
        while(doo){
            doo = false;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(cross && grid[i][j] == 'x'){
                        cout << i+1 << ' ' << j+1 << endl;
                        cross = false;
                        grid[i][j] = '.';
                        doo = true;
                    }
                    if(!cross && grid[i][j] == 'o'){
                        cout << i+1 << ' ' << j+1 << endl;
                        cross = true;
                        grid[i][j] = '.';
                        doo = true;
                    }
                }
            }
        }
        return 0;
    }

    char w = '.';
    pii am;
    if(a1.first != -1){
        am = a1;
        w = 'x';
    }else {
        am = a2;
        w = 'o';
    }

    am = {-1,-1};

    for(int ii = 0; ii < n; ii++){
        for(int jj = 0; jj < n; jj++){
            if(grid[ii][jj] != w) continue;
            bool aa = false;

            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    // bool pj = false;
                    if(i + k <= n){
                        bool pass = true;
                        for(int g = 0; g < k; g++){
                            if(grid[i+g][j] != w) pass = false;
                            if(i+g == ii && j == jj) pass = false;

                        }
                        if(pass) aa = true;
                    }

                    if(j + k <= n){
                        bool pass = true;
                        for(int g = 0; g < k; g++){
                            if(grid[i][j+g] != w) pass = false;
                            if(i == ii && j+g == jj) pass = false;
                        }
                        if(pass) aa = true;
                    }

                    if(i + k <= n && j + k <= n){
                        bool pass = true;
                        for(int g = 0; g < k; g++){
                            if(grid[i+g][j+g] != w) pass = false;
                            if(i+g == ii && j+g == jj) pass = false;
                        }
                        if(pass) aa = true;
                    }

                    if(i + k <= n && j - k >= -1){
                        bool pass = true;
                        for(int g = 0; g < k; g++){
                            if(grid[i+g][j-g] != w) pass = false;
                            if(i+g == ii && j-g == jj) pass = false;
                        }
                        if(pass) aa = true;
                    }

                }
            }

            if(aa){
                continue;
            }
            if(!aa){
                am = {ii,jj};
            }

        }
    }

    if(am.first == -1){
        cout << "NIE\n";
        return 0;
    }

    if((w == 'x' && cc1 < cc2) || (w == 'o' && cc2 < cc1)){
        cout << "NIE\n";
        return 0;
    }

    grid[am.first][am.second] = '.';

    cout << "TAK\n";
    vector<pair<int,int>> ans(0);

    bool cross = (w == 'x') ? false : true;
    bool doo = true;
    while(doo){
        doo = false;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(cross && grid[i][j] == 'x'){
                    ans.push_back(make_pair(i, j));
                    cross = false;
                    grid[i][j] = '.';
                    doo = true;
                }
                if(!cross && grid[i][j] == 'o'){
                    ans.push_back(make_pair(i, j));
                    cross = true;
                    grid[i][j] = '.';
                    doo = true;
                }
            }
        }
    }    

    reverse(ans.begin(), ans.end());

    ans.push_back(am);

    for(int i = 0; i < (int) ans.size(); i++){
        cout << ans[i].first+1 << ' ' << ans[i].second+1 << endl;
    }

    return 0;
}

int main(){
    fastio;

    int t = 1; 
    cin >> t;

    while(t--){
        solve();
    }

    return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3452kb

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

result:

ok correct (7 test cases)

Test #2:

score: 0
Accepted
time: 12ms
memory: 3456kb

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

result:

ok correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 23ms
memory: 3440kb

input:

10000
6 4
x.xx.o
xo.o.x
ooox.o
o..xo.
..xxxo
o.oxx.
6 5
oooxxx
oxoxxo
xoooxo
xoxxxx
xooxox
xoxxxx
6 3
o.x.x.
oo.o.x
xx.oo.
.x.xx.
ooxo..
.xxo..
6 6
xoo..o
o.xx.x
oooooo
xx.x..
o..xx.
...xxx
6 5
xooxoo
ooxxoo
xxooxx
oxooxx
oxoxxx
xxoxoo
6 5
xoxxxo
ooooxo
ooxoxx
oxxoox
xxxxox
ooooxo
6 5
o....o
.ox.oo
...

output:

TAK
4 1
1 4
3 3
1 3
6 3
5 5
3 2
1 1
6 1
5 4
2 4
6 5
5 6
5 3
4 5
4 4
3 6
3 4
3 1
2 6
2 2
2 1
1 6
6 4
NIE
TAK
4 5
5 4
3 2
2 4
6 3
5 2
4 4
3 5
3 1
2 2
1 5
6 4
6 2
5 1
4 2
3 4
2 6
2 1
1 3
1 1
5 3
NIE
TAK
1 1
1 2
1 4
1 5
2 3
2 5
3 1
3 3
3 5
4 1
4 2
4 3
4 5
5 1
5 2
5 3
5 4
6 3
6 4
6 5
2 4
2 6
3 2
3 4
3 6
...

result:

ok correct (10000 test cases)
English 繁體中文 简体中文

服务器时间: 2024-12-05 06:53:26 | 开源项目