QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#239865 | #5509. Kooky Tic-Tac-Toe | KLPP# | RE | 0ms | 3584kb | C++20 | 3.0kb | 2023-11-05 00:00:49 | 2023-11-05 00:00:50 |
Judging History
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define all(x) begin(x),end(x)
void solve(int testcase){
int n,K;
cin>>n>>K;
vector<string> a(n);
for(auto&i:a)cin>>i;
//if(testcase!=1)return;
auto isfull=[&]()
{
for(auto x:a)for(auto i:x)if(i=='.')return false;
return true;
};
auto forward=[&](int x,int y,int dx,int dy)
{
if(x+(K-1)*dx>=n)return false;
if(y+(K-1)*dy>=n)return false;
if(x+(K-1)*dx<0)return false;
if(y+(K-1)*dy<0)return false;
if(a[x][y]=='.')return false;
bool ispossible=true;
int j=0;
for(int i=0;i<K;i++){
ispossible&=a[x][y]==a[x+i*dx][y+i*dy];
}
return ispossible;
};
auto someonewon=[&]()
{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(forward(i,j,1,0))return true;
if(forward(i,j,0,1))return true;
if(forward(i,j,1,1))return true;
if(forward(i,j,-1,1))return true;
}
}
return false;
};
auto isover=[&]()
{
return isfull()||someonewon();
};
if(!isover()){
cout<<"NIE\n";
return;
}
array<int,2> lastpos;
bool ispossible=false;
char empty='.';
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
swap(empty,a[i][j]);
//for(auto&k:a)cout<<k<<'\n';
//cout<<isover()<<'\n';
//cout<<someonewon()<<'\n';
if(!isover()){
ispossible=true;
lastpos={i,j};
}
swap(empty,a[i][j]);
}
}
if(!ispossible){
cout<<"NIE\n";
return;
}
int c0s=0;
int c1s=0;
array<int,2> random0pos;
array<int,2> random1pos;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='o'){
random0pos={i,j};
c0s++;
}
else if(a[i][j]=='x'){
random1pos={i,j};
c1s++;
}
}
}
if(abs(c0s-c1s)>1){
cout<<"NIE\n";
return;
}
if(someonewon()){
if(c0s<c1s&&a[lastpos[0]][lastpos[1]]=='o'){
cout<<"NIE\n";
return;
}
else if(c1s<c0s&&a[lastpos[0]][lastpos[1]]=='x'){
cout<<"NIE\n";
return;
}
}
else if(c0s>c1s){
lastpos=random0pos;
}
else if(c1s>c0s){
lastpos=random1pos;
}
else{
assert(false);
}
cout<<"TAK\n";
vector<array<int,2>> S;
S.push_back(lastpos);
swap(a[lastpos[0]][lastpos[1]],empty);
vector<array<int,2>> p0s;
vector<array<int,2>> p1s;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='o')p0s.push_back({i,j});
if(a[i][j]=='x')p1s.push_back({i,j});
}
}
if(empty=='o')swap(p0s,p1s);
while(p0s.size()){
S.push_back(p0s.back());
p0s.pop_back();
swap(p0s,p1s);
}
assert(p1s.size()==0);
reverse(all(S));
for(auto[x,y]:S){
cout<<x+1<<' '<<y+1<<'\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;
cin>>tt;
for(int i=0;i<tt;i++){
solve(i);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
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 1 3 1 2 2 3 3 2 3 TAK 1 1 2 4 1 2 3 3 1 4 4 2 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
Runtime Error
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 ...