QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#88188#5509. Kooky Tic-Tac-Toemeaningful#WA 4ms3632kbC++143.9kb2023-03-15 14:52:122023-03-15 14:52:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-15 14:52:16]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3632kb
  • [2023-03-15 14:52:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
template<class T>inline void read(T &x) {
    x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) f|=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);
    if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int fx[4] = {1,1,1,0};
int fy[4] = {1,-1,0,1};
const int N = 8;
int n,k;
int a[N][N];

inline bool in(int x,int y) {
    return x > 0 && x <= n && y > 0 && y <= n;
}
inline int check_status() {
    bool bb[2] = {0,0};
    fo(i,1,n)
        fo(j,1,n) {
            fo(d,0,3) {
                bool flag = 1;
                if(a[i][j] == -1) {
                    flag = 0;
                }
                ff(l,1,k) {
                    int x = i + fx[d] * l;
                    int y = j + fy[d] * l;
                    if(!in(x,y)) {
                        flag = 0; break;
                    }
                    if(a[x][y] != a[i][j]) {
                        flag = 0; break;
                    }
                }
                if(flag)
                    bb[a[i][j]] = 1;
            }
        }
    return bb[0] | (bb[1] << 1);
}

char s[N+5];
void Solve() {
    read(n,k);
    auto id = [&](const char &c) -> int {
        if(c == '.')
            return -1;
        return c == 'x';
    };
    bool bo = 0;
    int cnt[2] = {0,0};
    vector<pair<int,int>> adj[2];
    fo(i,1,n) {
        scanf("%s",s+1);
        fo(j,1,n) {
            a[i][j] = id(s[j]);
            bo |= (a[i][j] == -1);
            if(a[i][j] != -1) {
                cnt[a[i][j]] ++;
                adj[a[i][j]].push_back({i,j});
            }
        }
    }
    if(abs(cnt[0]-cnt[1]) > 1) return (void)(puts("NIE"));
    int d = cnt[1] > cnt[0];
    auto print = [&]() -> void {
        printf("TAK\n");
        int i = 0;
        for(;i < adj[d].size() && i < adj[1-d].size();i ++) {
            printf("%d %d\n%d %d\n",adj[d][i].fi,adj[d][i].se,adj[1-d][i].fi,adj[1-d][i].se);
        }
        if(adj[d].size() > adj[1-d].size())
            printf("%d %d\n",adj[d].back().fi,adj[d].back().se);
    };
    int st = check_status();
    if(st == 3) return (void)(puts("NIE"));
    if(st == 0) {
        if(bo)
            return (void)(puts("NIE"));
        else
            print();
        return;
    }
    if(st == 1 && cnt[0] < cnt[1]) return (void)(puts("NIE"));
    if(st == 2 && cnt[0] > cnt[1]) return (void)(puts("NIE"));
    if(st == 1) d = 1;
    else d = 0;
    if(cnt[0] != cnt[1])
        d = 1-d;
    fo(i,1,n)
        fo(j,1,n)
            if(a[i][j] != -1) {
                int x = a[i][j];
                a[i][j] = -1;
                int ft = check_status();
                //cerr<<i<<' '<<j<<' '<<ft<<endl;
                a[i][j] = x;
                if(ft == 0) {
                    ff(k,0,adj[x].size()-1)
                        if(adj[x][k].fi == i && adj[x][k].se == j) {
                            swap(adj[x][k],adj[x][cnt[x]-1]);
                            break;
                        }
                    print();
                    return;
                }
            }
}
int main() {
    int T = 1;
    read(T);
    for(;T--;) Solve();
    return 0;
}

详细

Test #1:

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

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 3
3 1
2 2
3 3
2 1
TAK
1 1
4 2
1 2
3 3
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: 4ms
memory: 3536kb

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 3
3 1
2 2
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 3
3 1
1 2
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 3
3 1
4 2
3 2
4 1
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 output format Expected integer, but "NIE" found (test case 57)