QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165691#5509. Kooky Tic-Tac-Toearseny_y#WA 12ms3868kbC++233.6kb2023-09-05 20:51:142023-09-05 20:51:14

Judging History

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

  • [2023-09-05 20:51:14]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:3868kb
  • [2023-09-05 20:51:14]
  • 提交

answer

//I wrote this code 4 u today
#include <bits/stdc++.h>

template<class t> using vc = std::vector<t>;

#define nd node*
#define pnd pair<nd, nd>

typedef long long ll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    std::sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(std::unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    std::reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

typedef long double ld;
using namespace std;

void solve(){
    int n, k;
    cin >> n >> k;
    vector<string> a(n + 2);

    vector<vector<pair<int, int>>> res(2);
    map<int, int> id = {{'o', 0}, {'x',1}};
    int nn = 0;
    for(int i=1;i<=n;++i){
        cin >> a[i];
        a[i] = "#" + a[i] + "#";
        for(int j=1;j<=n;++j){
            if(a[i][j] != '.'){
                nn++;
                res[id[a[i][j]]].push_back({i,j});
            }
        }
    }
    for(int i=0;i<n+2;++i){
        a[0] += "#", a[n+1] += "#";
    }

    if(abs((int)(res[0].size())-(int)(res[1].size()))>1){
        cout << "NIE";
        return;
    }

    vector<vector<int>> start;
    vector<int> dx = {1, 1, 1, 0};
    vector<int> dy = {-1, 0, 1, 1};
    auto checkr = [&](int i, int j){
        int ci = i, cj = j;
        for(int t=0;t<4;++t){
            bool fl = true;
            i = ci, j = cj;
            char sym = a[ci][cj];
            for(int len=0;len<k;++len){
                if(a[i][j] == '#' || a[i][j] == '.'){
                    fl = false;
                    break;
                }
                if(a[i][j] != sym) {
                    fl = false;
                    break;
                }
                i += dx[t], j += dy[t];
            }
            if(fl){
                start.push_back({t, ci, cj});
            }
        }
    };

    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            checkr(i, j);
        }
    }

    if(start.size() == 0){

        if(nn == n * n){
            cout << "TAK\n";
            if(res[0].size()<res[1].size()) swap(res[0], res[1]);
            vector<int> ind(2, 0);
            for(int i=0;i<n*n;++i){
                auto x = res[i%2][ind[i%2]++];
                cout << x.first << ' ' << x.second << "\n";
            }
        } else{
            cout << "NIE";
        }
    } else if(start.size() == 1){
        int st = id[a[start[0][1]][start[0][2]]];
        pair<int, int> y = {start[0][1], start[0][2]};
        vector<vector<pair<int, int>>> ans = {res[st], res[!st]};
        if(res[st].size() == res[!st].size()){
            ans = {res[!st], res[st]};
        } else if(res[st].size() < res[!st].size()){
            cout << "NIE";
            return;
        }
        cout << "TAK\n";
        vector<int> ind(2, 0);
        for(int i=0;i<nn;++i){
            auto x = ans[i%2][ind[i%2]++];
            if(x == y){
                i++;
                nn++;
                continue;
            }
            cout << x.first << ' ' << x.second << "\n";
        }
        cout << y.first << ' ' << y.second;
    } else{
        cout << "NIE";
    }
}

int main() {
    std::cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(18);
    int t;
    cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }
}

详细

Test #1:

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

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: 12ms
memory: 3868kb

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

result:

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