QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#239898#5509. Kooky Tic-Tac-ToeKLPP#RE 1ms3532kbC++202.9kb2023-11-05 00:19:392023-11-05 00:19:39

Judging History

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

  • [2023-11-05 00:19:39]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3532kb
  • [2023-11-05 00:19:39]
  • 提交

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=1;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]);
	    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);
    }
    

    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);
    }
    if(p1s.size()!=0){
	cout<<"NIE\n";
	return;
    }

    cout<<"TAK\n";
    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: 1ms
memory: 3532kb

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
...

output:


result: