QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#88188 | #5509. Kooky Tic-Tac-Toe | meaningful# | WA | 4ms | 3632kb | C++14 | 3.9kb | 2023-03-15 14:52:12 | 2023-03-15 14:52:16 |
Judging History
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)