QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #607893 | #5509. Kooky Tic-Tac-Toe | hzy99999# | WA | 9ms | 3832kb | C++20 | 6.9kb | 2024-10-03 16:56:07 | 2024-10-03 16:56:07 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int T;
int n, k;
string s[10];
int a[10][10];
int check(int sx, int sy, int ex, int ey){//k
bool flagx = 1, flago = 1;
if(sx == ex) {
for (int i = sy; i <= ey; i++) {
flagx &= (s[sx][i] == 'x');
flago &= (s[sx][i] == 'o');
}
if (flagx)return 1;
else if (flago)return -1;
}
else if (sy == ey) {
for (int i = sx; i <= ex; i++) {
flagx &= (s[i][sy] == 'x');
flago &= (s[i][sy] == 'o');
}
if (flagx)return 1;
else if (flago)return -1;
}
else {
int dx = 0, dy = 0;
if (sx < ex)dx = 1;
else dx = -1;
if (sy < ey)dy = 1;
else dy = -1;
for (int x = sx, y = sy; x != ex; x += dx, y += dy) {
flagx &= (s[x][y] == 'x');
flago &= (s[x][y] == 'o');
}
flagx &= (s[ex][ey] == 'x');
flago &= (s[ex][ey] == 'o');
if (flagx)return 1;
else if (flago)return -1;
}
return 0;
}
int win() {
int winx = 0, wino = 0;
for (int i = 1; i <= n; i++) {
int sumx = 0, sumo = 0;
for (int j = 1; j + k - 1 <= n; j++) {
int t = check(i, j, i, j + k - 1);
if (t == 1)winx++;
else if (t == -1)wino++;
}
}
for (int j = 1; j <= n; j++) {
int sumx = 0, sumo = 0;
for (int i = 1; i + k - 1 <= n; i++) {
int t = check(i, j, i + k - 1, j);
if (t == 1)winx++;
else if (t == -1)wino++;
}
}
int dx[4] = { 1,1,-1,-1 };
int dy[4] = { 1,-1,1,-1 };
PII t;
int uu = 0, vv = 0;
for (t.x = 1; t.x <= n; t.x++) {
for (t.y = 1; t.y <= n; t.y++) {
for (int i = 0; i < 4; i++) {
int nx = dx[i] * (k - 1) + t.x;
int ny = dy[i] * (k - 1) + t.y;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
int tt = check(t.x, t.y, nx, ny);
if (tt == 1)uu++;
else if (tt == -1)vv++;
}
}
}
}
winx += uu / 2;
wino += vv / 2;
//cout << "winx" << winx << " " << "winy" << wino << '\n';
if (winx && wino)return -2;
else if (winx)return 1;
else if (wino)return -1;
return 0;
}
int find(PII t) {
int dx[8] = { 1,1,1,0,0,-1,-1,-1 };
int dy[8] = { 1,0,-1,1,-1,1,0,-1 };
for (int i = 0; i < 8; i++) {
int nx = dx[i] * (k - 1) + t.x;
int ny = dy[i] * (k - 1) + t.y;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
if (check(t.x, t.y, nx, ny))
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--){
cin >> n >> k;
vector<PII>X, O;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] = " " + s[i];
for (int j = 1; j <= n; j++) {
a[i][j] = -1;
if (s[i][j] == 'x')X.push_back({ i,j });
if (s[i][j] == 'o')O.push_back({ i,j });
}
}
int winner = win();
if (abs((int)(X.size() - O.size())) > 1) {
cout << "NIE\n";
continue;
}
else if ((X.size() + O.size()) != n * n && !winner) {
cout << "NIE\n";
continue;
}
else if (abs(winner) > 1) {
cout << "NIE\n";
continue;
}
vector<PII>ans;
if (X.size() > O.size()) {
if (winner == -1) {
cout << "NIE" << '\n';
continue;
}
else if (winner == 0) {
for (int i = 0; i < O.size(); i++) {
ans.push_back(X[i]);
ans.push_back(O[i]);
}
ans.push_back(X[O.size()]);
}
else {
for (int i = 0; i < X.size(); i++) {
if (find(X[i])) {
auto t = X[i];
X.erase(X.begin() + i);
X.push_back(t);
}
}
for (int i = 0; i < O.size(); i++) {
ans.push_back(X[i]);
ans.push_back(O[i]);
}
ans.push_back(X[O.size()]);
}
}else if (X.size() == O.size()) {
if (winner == 0) {
for (int i = 0; i < O.size(); i++) {
ans.push_back(X[i]);
ans.push_back(O[i]);
}
}
else if (winner == 1) {
for (int i = 0; i < X.size(); i++) {
if (find(X[i])) {
auto t = X[i];
X.erase(X.begin() + i);
X.push_back(t);
}
}
for (int i = 0; i < O.size(); i++) {
ans.push_back(O[i]);
ans.push_back(X[i]);
}
}
else {
for (int i = 0; i < O.size(); i++) {
if (find(O[i])) {
auto t = O[i];
O.erase(O.begin() + i);
O.push_back(t);
}
}
for (int i = 0; i < O.size(); i++) {
ans.push_back(X[i]);
ans.push_back(O[i]);
}
}
}
else {// X<0
if (winner == 1) {
cout << "NIE" << '\n';
continue;
}
else if (winner == 0) {
for (int i = 0; i < X.size(); i++) {
ans.push_back(O[i]);
ans.push_back(X[i]);
}
ans.push_back(O[X.size()]);
}
else {
for (int i = 0; i < O.size(); i++) {
if (find(O[i])) {
auto t = O[i];
O.erase(O.begin() + i);
O.push_back(t);
}
}
for (int i = 0; i < X.size(); i++) {
ans.push_back(O[i]);
ans.push_back(X[i]);
}
ans.push_back(O[X.size()]);
}
}
cout << "TAK\n";
for (auto t : ans) {
cout << t.x << " " << t.y << '\n';
}
}
return 0;
}
/*
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3832kb
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 1 3 3 2 3 TAK 1 1 3 3 1 2 2 4 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
Wrong Answer
time: 9ms
memory: 3640kb
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 1 3 3 2 3 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 1 3 2 1 3 NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK 1 2 1 1 1 3 2 2 2 3 4 2 2 4 1 4 3 1 4 3 3 2 4 1 NIE NIE NIE NIE NIE TAK 2 1 1 2 2 3 1 3 2 4 2 2 3 1 3 2 3 3 4 3 ...
result:
wrong answer Contestant's solution makes an incorrect last move (test case 31)