QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333854 | #4325. Kraljice | ivanj | 0 | 0ms | 3500kb | C++14 | 2.1kb | 2024-02-20 18:00:26 | 2024-02-20 18:00:27 |
answer
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 1025;
int n;
int r[maxn];
int c[maxn];
int d1[maxn];
int d2[maxn];
vector<ii> ans;
int check(int x, int y) {
return (r[x] + c[y] + d1[x + y] + d2[x - y + n] + 1) % 2;
}
int play(int x, int y) {
if(!check(x, y)) {
cout << "err\n";
exit(0);
}
ans.pb({x, y});
r[x]++, c[y]++, d1[x + y]++, d2[x - y + n]++;
}
void print() {
for(int i = 0;i < n;i++, cout << "\n")
for(int j = 0;j < n;j++) {
cout << (r[i] + c[j] + d1[i + j] + d2[i - j + n]) % 2 << " ";
}
cout << "..................................\n";
}
void resi4() {
play(0, 1);
play(1, 3);
play(0, 2);
play(1, 0);
play(1, 1);
play(2, 3);
play(0, 3);
play(2, 0);
play(2, 1);
play(2, 2);
play(3, 0);
play(3, 2);
play(3, 1);
play(3, 3);
}
void resi3() {
play(1, 2);
play(2, 0);
play(1, 1);
play(0, 0);
play(2, 2);
play(2, 1);
play(0, 1);
play(0, 2);
play(1, 0);
}
void rek(int n) {
if(n <= 2) {play(0, 0);return;}
if(n == 3) {resi3();return;}
if(n == 4) {resi4();return;}
rek(n - 2);
for(int i = 0;i < n - 3;i++) {
if(check(i, n - 1))
play(i, n - 1), play(i, n - 2);
else play(i, n - 2), play(i, n - 1);
if(check(n - 1, i))
play(n - 1, i), play(n - 2, i);
else play(n - 2, i), play(n - 1, i);
}
if(n % 2 == 1) {
play(n - 2, n - 1);
play(n - 3, n - 2);
play(n - 1, n - 2);
play(n - 2, n - 2);
play(n - 3, n - 1);
play(n - 1, n - 3);
play(n - 2, n - 3);
play(n - 1, n - 1);
} else {
play(n - 3, n - 1);
play(n - 3, n - 2);
play(n - 2, n - 1);
play(n - 2, n - 3);
play(n - 1, n - 3);
play(n - 2, n - 2);
play(n - 1, n - 2);
play(n - 1, n - 1);
}
}
int main() {
cin >> n;
if(n <= 2) {
cout << "1\n1 1\n";
return 0;
}
rek(n);
cout << ans.size() << "\n";
for(ii p : ans)
cout << p.x + 1 << " " << p.y + 1 << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Memory Limit Exceeded
Test #1:
score: 6
Accepted
time: 0ms
memory: 3500kb
input:
1
output:
1 1 1
result:
ok 1 queen(s)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
2
output:
1 1 1
result:
ok 1 queen(s)
Test #3:
score: -6
Memory Limit Exceeded
input:
3
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%