QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95965#5575. Knight's Tour Reduxaguo123TL 2ms5424kbC++141.5kb2023-04-12 18:58:542023-04-12 18:58:55

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-12 18:58:55]
  • Judged
  • Verdict: TL
  • Time: 2ms
  • Memory: 5424kb
  • [2023-04-12 18:58:54]
  • Submitted

answer

#include<iostream>
#include<string>
#include <cstring>
#include <vector>
#include<algorithm>
using namespace  std;
typedef  long long LL;
typedef  pair<int,int> PII;
const LL N=1e6+10,mod=998244353;
int n;
int m;
string s;
int a[1000010];
LL cnt1[200],cnt2[200];
bool col[N],row[N];
int num,vis;
vector<PII>ans;
int dx[]={1,3,3,1,-1,-3,-3,-1},dy[]={3,1,-1,-3,-3,-1,1,3};
void dfs(int x,int y){
    if(vis)return;
    if(x<1||x>n||y<1||y>n)return;
    if(col[x]||row[y])return;
    num++;
    col[x]=row[y]=1;
    ans.push_back({x,y});
    if(num==n){
       for(auto k:ans)
           cout<<k.first<<' '<<k.second<<endl;
       vis=1;
        return ;
    }
    for(int i=0;i<8;i++)
        dfs(x+dx[i],y+dy[i]);
        col[x]=row[y]=0;
        num--;
        ans.pop_back();
}
int main()
{   //LL ans=0;
    cin>>n;
    if(n==1){
        puts("POSSIBLE");
        cout<<1<<' '<<1<<endl;
        return  0;
    }else if(n<5){puts("IMPOSSIBLE");return 0;}

    puts("POSSIBLE");

    int pos=0;
    while(pos+18<n){
        cout<<pos+1<<' '<<pos+3<<endl;
        cout<<pos+4<<' '<<pos+2<<endl;
        cout<<pos+7<<' '<<pos+1<<endl;
        cout<<pos+6<<' '<<pos+4<<endl;
        cout<<pos+3<<' '<<pos+5<<endl;
        cout<<pos+2<<' '<<pos+8<<endl;
        cout<<pos+5<<' '<<pos+7<<endl;
        cout<<pos+8<<' '<<pos+6<<endl;
        cout<<pos+9<<' '<<pos+9<<endl;

        for(int i=1;i<=9;i++)col[pos+i]=row[pos+i]=1,num++;
        pos+=9;
    }
    dfs(pos+1,pos+3);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3492kb

input:

1

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0
Accepted
time: 2ms
memory: 3356kb

input:

2

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0
Accepted
time: 2ms
memory: 3348kb

input:

3

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0
Accepted
time: 2ms
memory: 3316kb

input:

4

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0
Accepted
time: 0ms
memory: 3388kb

input:

5

output:

POSSIBLE
1 3
4 4
5 1
2 2
3 5

result:

ok answer = 1

Test #6:

score: 0
Accepted
time: 1ms
memory: 3384kb

input:

6

output:

POSSIBLE
1 3
2 6
5 5
6 2
3 1
4 4

result:

ok answer = 1

Test #7:

score: 0
Accepted
time: 2ms
memory: 3496kb

input:

7

output:

POSSIBLE
1 3
2 6
5 7
6 4
7 1
4 2
3 5

result:

ok answer = 1

Test #8:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

8

output:

POSSIBLE
1 3
2 6
5 7
8 8
7 5
6 2
3 1
4 4

result:

ok answer = 1

Test #9:

score: 0
Accepted
time: 1ms
memory: 3396kb

input:

9

output:

POSSIBLE
1 3
2 6
3 9
6 8
9 7
8 4
7 1
4 2
5 5

result:

ok answer = 1

Test #10:

score: 0
Accepted
time: 0ms
memory: 3388kb

input:

10

output:

POSSIBLE
1 3
2 6
3 9
6 10
7 7
10 8
9 5
8 2
5 1
4 4

result:

ok answer = 1

Test #11:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

11

output:

POSSIBLE
1 3
4 4
5 7
2 8
3 11
6 10
9 9
10 6
7 5
8 2
11 1

result:

ok answer = 1

Test #12:

score: 0
Accepted
time: 2ms
memory: 3360kb

input:

12

output:

POSSIBLE
1 3
4 4
5 1
8 2
9 5
12 6
11 9
10 12
7 11
6 8
3 7
2 10

result:

ok answer = 1

Test #13:

score: 0
Accepted
time: 2ms
memory: 3396kb

input:

13

output:

POSSIBLE
1 3
2 6
5 7
4 4
3 1
6 2
7 5
8 8
9 11
12 12
13 9
10 10
11 13

result:

ok answer = 1

Test #14:

score: 0
Accepted
time: 2ms
memory: 3372kb

input:

14

output:

POSSIBLE
1 3
2 6
5 7
6 10
3 11
4 14
7 13
10 12
11 9
14 8
13 5
12 2
9 1
8 4

result:

ok answer = 1

Test #15:

score: 0
Accepted
time: 2ms
memory: 3364kb

input:

15

output:

POSSIBLE
1 3
2 6
3 9
6 10
7 13
4 12
5 15
8 14
9 11
10 8
13 7
14 4
15 1
12 2
11 5

result:

ok answer = 1

Test #16:

score: 0
Accepted
time: 0ms
memory: 3380kb

input:

16

output:

POSSIBLE
1 3
2 6
3 9
4 12
5 15
8 16
9 13
6 14
7 11
10 10
11 7
14 8
15 5
16 2
13 1
12 4

result:

ok answer = 1

Test #17:

score: 0
Accepted
time: 0ms
memory: 3384kb

input:

17

output:

POSSIBLE
1 3
2 6
3 9
6 8
5 5
4 2
7 1
8 4
9 7
10 10
11 13
12 16
15 17
16 14
17 11
14 12
13 15

result:

ok answer = 1

Test #18:

score: 0
Accepted
time: 0ms
memory: 3372kb

input:

18

output:

POSSIBLE
1 3
2 6
3 9
4 12
7 13
8 16
5 15
6 18
9 17
10 14
11 11
14 10
15 7
18 8
17 5
16 2
13 1
12 4

result:

ok answer = 1

Test #19:

score: 0
Accepted
time: 2ms
memory: 5408kb

input:

19

output:

POSSIBLE
1 3
4 2
7 1
6 4
3 5
2 8
5 7
8 6
9 9
10 12
11 15
12 18
15 19
16 16
19 17
18 14
17 11
14 10
13 13

result:

ok answer = 1

Test #20:

score: 0
Accepted
time: 2ms
memory: 5424kb

input:

20

output:

POSSIBLE
1 3
4 2
7 1
6 4
3 5
2 8
5 7
8 6
9 9
10 12
13 13
14 16
11 17
12 20
15 19
18 18
19 15
16 14
17 11
20 10

result:

ok answer = 1

Test #21:

score: -100
Time Limit Exceeded

input:

99990

output:

POSSIBLE
1 3
4 2
7 1
6 4
3 5
2 8
5 7
8 6
9 9
10 12
13 11
16 10
15 13
12 14
11 17
14 16
17 15
18 18
19 21
22 20
25 19
24 22
21 23
20 26
23 25
26 24
27 27
28 30
31 29
34 28
33 31
30 32
29 35
32 34
35 33
36 36
37 39
40 38
43 37
42 40
39 41
38 44
41 43
44 42
45 45
46 48
49 47
52 46
51 49
48 50
47 53
50 ...

result: