QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#165691 | #5509. Kooky Tic-Tac-Toe | arseny_y# | WA | 12ms | 3868kb | C++23 | 3.6kb | 2023-09-05 20:51:14 | 2023-09-05 20:51:14 |
Judging History
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)