QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #915865 | #5575. Knight's Tour Redux | tsai | WA | 0ms | 3840kb | C++14 | 4.8kb | 2025-02-26 16:40:47 | 2025-02-26 16:40:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[33];
void solve(){
int n;
scanf("%d",&n);
if(n==1){
printf("POSSIBLE\n1 1");
return ;
}else if(n==12){
printf("POSSIBLE\n5 3\n2 4\n1 1\n4 2\n3 5\n");
printf("6 6\n9 7\n12 8\n11 11\n8 12\n7 9\n10 10\n");
return ;
}else if(n>11&&(n-11)%9==0&&(n-11)%18!=0){
printf("POSSIBLE\n5 3\n2 4\n1 1\n4 2\n3 5\n");
int x=6,y=6;
int jd=0,jd1=0;
int cnt=1,k=1;
for(int i=1;i<=n-5;i++){
printf("%d %d\n",x,y);
k++;
cnt++;
if(k%9==0){
k=0;
x++;y+=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
if(cnt%3==0){
if(jd1==0){
x+=3;y++;
}else if(jd1==1){
x+=3;y--;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x++;y+=3;
}else if(jd==1){
x--;y-=3;
}
}
printf("%d %d\n",n-3,n-5);
printf("%d %d\n",n,n-4);
printf("%d %d\n",n-1,n-1);
printf("%d %d\n",n-4,n);
printf("%d %d\n",n-5,n-3);
printf("%d %d\n",n-2,n-2);
return ;
}
if(n%9==0){
printf("POSSIBLE\n");
int x=n,y=n;
int k=0;
int jd=0;
int jd1=0;
int cnt=0;
for(int i=1;i<=n;i++){
printf("%d %d\n",x,y);
k++;
if(k%9==0){
k=0;
x--;
y-=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
cnt++;
if(cnt%3==0){
if(jd1==0){
x-=3;
y--;
}else if(jd1==1){
x-=3;
y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x--;
y-=3;
}else if(jd==1){
y+=3;
x++;
}
}
}else if(n%9==1){
printf("POSSIBLE\n");
int x=2,y=4;
int jd=0,jd1=0;
int cnt=0,k=0;
printf("1 1\n");
for(int i=2;i<=n;i++){
printf("%d %d\n",x,y);
k++;
cnt++;
if(k%9==0){
k=0;
x++;y+=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
if(cnt%3==0){
if(jd1==0){
x+=3;y--;
}else if(jd1==1){
x+=3;y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x++;y+=3;
}else if(jd==1){
x--;y-=3;
}
}
}else if(n%9==8){
printf("POSSIBLE\n");
int x=n,y=n-2;
int jd=0,jd1=0;
int cnt=1,k=1;
for(int i=1;i<=n;i++){
printf("%d %d\n",x,y);
k++;
if(k%9==0){
k=0;
x--;
y-=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
cnt++;
if(cnt%3==0){
if(jd1==0){
x-=3;
y--;
}else if(jd1==1){
x-=3;
y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x--;
y-=3;
}else if(jd==1){
y+=3;
x++;
}
}
// printf("%d %d\n",n,n);
}else if(n%9==7){
printf("POSSIBLE\n");
printf("%d %d\n",n-2,n-2);
printf("%d %d\n",n-5,n-3);
printf("%d %d\n",n-4,n);
printf("%d %d\n",n-1,n-1);
printf("%d %d\n",n,n-4);
printf("%d %d\n",n-3,n-5);
printf("%d %d\n",n-6,n-6);
int x=n-7,y=n-9;
int k=0;
int jd=0;
int jd1=1;
int cnt=0;
for(int i=1;i<=n-7;i++){
printf("%d %d\n",x,y);
k++;
if(k%9==0){
k=0;
x--;
y-=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
cnt++;
if(cnt%3==0){
if(jd1==0){
x-=3;
y--;
}else if(jd1==1){
x-=3;
y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x--;
y-=3;
}else if(jd==1){
y+=3;
x++;
}
}
}else if(n%9==5||(n%9==4&&n>9&&(n-4)%18!=0)){
printf("POSSIBLE\n5 3\n2 4\n1 1\n4 2\n3 5\n");
int x=6,y=6;
int jd=0,jd1=0;
int cnt=0,k=0;
for(int i=1;i<=n-5;i++){
printf("%d %d\n",x,y);
k++;
cnt++;
if(k%9==0){
k=0;
x++;y+=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
if(cnt%3==0){
if(jd1==0){
x+=3;y++;
}else if(jd1==1){
x+=3;y--;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x++;y+=3;
}else if(jd==1){
x--;y-=3;
}
}
}else if(n%9==6){
printf("POSSIBLE\n");
printf("%d %d\n",n-2,n-2);
printf("%d %d\n",n-5,n-3);
printf("%d %d\n",n-4,n);
printf("%d %d\n",n-1,n-1);
printf("%d %d\n",n,n-4);
printf("%d %d\n",n-3,n-5);
int x=n-6,y=n-6;
int k=0;
int jd=0;
int jd1=0;
int cnt=0;
for(int i=1;i<=n-6;i++){
printf("%d %d\n",x,y);
k++;
if(k%9==0){
k=0;
x--;
y-=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
cnt++;
if(cnt%3==0){
if(jd1==0){
x-=3;
y--;
}else if(jd1==1){
x-=3;
y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x--;
y-=3;
}else if(jd==1){
y+=3;
x++;
}
}
}else{
printf("IMPOSSIBLE");
}
return ;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
1
output:
POSSIBLE 1 1
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
2
output:
IMPOSSIBLE
result:
ok answer = 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3
output:
IMPOSSIBLE
result:
ok answer = 0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
4
output:
IMPOSSIBLE
result:
ok answer = 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
5
output:
POSSIBLE 5 3 2 4 1 1 4 2 3 5
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
6
output:
POSSIBLE 4 4 1 3 2 6 5 5 6 2 3 1
result:
ok answer = 1
Test #7:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
7
output:
POSSIBLE 5 5 2 4 3 7 6 6 7 3 4 2 1 1
result:
ok answer = 1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
8
output:
POSSIBLE 8 6 7 3 4 2 5 5 6 8 3 7 2 4 1 1
result:
ok answer = 1
Test #9:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
9
output:
POSSIBLE 9 9 8 6 7 3 4 2 5 5 6 8 3 7 2 4 1 1
result:
ok answer = 1
Test #10:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
10
output:
POSSIBLE 1 1 2 4 3 7 4 10 7 9 6 6 5 3 8 2 9 5 10 8
result:
ok answer = 1
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3840kb
input:
11
output:
IMPOSSIBLE
result:
wrong answer jury has the better answer: jans = 1, pans = 0 (1 is Possible)