QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252042#7619. Make SYSU Great Again Iucup-team045#AC ✓315ms63808kbC++203.4kb2023-11-15 15:05:312023-11-15 15:05:31

Judging History

你现在查看的是最新测评结果

  • [2023-11-15 15:05:31]
  • 评测
  • 测评结果：AC
  • 用时：315ms
  • 内存：63808kb
查看
  • [2023-11-15 15:05:31]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<set> 
#include<numeric>
#include<algorithm>
#include<cassert>
#include<set>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;
    vector<pair<int, int> > ans(k + 1);
    int st = 1, cur = 0;
    if (n % 3 == 1){
        st = 5;
        cur = 8;
        ans[1] = {1, 1};
        ans[2] = {1, 2};
        ans[3] = {2, 2};
        ans[4] = {2, 1};
        ans[5] = {3, 3};
        ans[6] = {3, 4};
        ans[7] = {4, 4};
        ans[8] = {4, 3};
    }
    else if (n % 3 == 2){
        st = 3;
        cur = 4;
        ans[1] = {1, 1};
        ans[2] = {1, 2};
        ans[3] = {2, 2};
        ans[4] = {2, 1};
    }
    for(int i = st; i <= n; i += 3){
        int l = i;
        ans[++cur] = {l, l + 2};
        ans[++cur] = {l + 1, l + 2};
        ans[++cur] = {l, l};
        ans[++cur] = {l + 1, l + 1};
        ans[++cur] = {l + 2, l};
        ans[++cur] = {l + 2, l + 1};
    }
    set<pair<int, int> > s(ans.begin(), ans.end());
    vector<int> g1(n + 1), g2(n + 1);
    for(int i = 1; i <= k; i++){
        auto [x, y] = ans[i];
        g1[x] = gcd(i, g1[x]);
        g2[y] = gcd(i, g2[y]);
    }
    vector<int> row1, row2;
    for(int i = 1; i <= n; i++){
        if (g1[i] != 1){
            row1.push_back(i);
        }
        else{
            row2.push_back(i);
        }
    }

    vector<int> odd, even;
    for(int i = 2 * n + 1; i <= k; i++){
        if (i % 2 == 0){
            even.push_back(i);
        }
        else{
            odd.push_back(i);
        }
    }
    while(odd.size() >= 2 && !row1.empty()){
        int t = row1.back();
        row1.pop_back();
        row2.push_back(t);
        int t1 = odd.back();
        odd.pop_back();
        int t2 = odd.back();
        odd.pop_back();
        ans[t1] = {t, t - 1};
        ans[t2] = {t - 1, t};
        s.insert({t, t - 1});
        s.insert({t - 1, t});
    }
    even.insert(even.end(), odd.begin(), odd.end());
    for(auto x : row2){
        for(auto y : row2){
            if (even.empty()) break;
            if (!s.contains({x, y})){
                s.insert({x, y});
                ans[even.back()] = {x, y};
                even.pop_back();
            }
        }
        if (even.empty()) break;
    }
    // even.insert(even.end(), odd.begin(), odd.end());
    
    // for(auto x : row2){
    //     for(auto y : row2){
    //         if (even.empty()) break;
    //         if (!s.contains({x, y})){
    //             s.insert({x, y});
    //             ans[even.back()] = {x, y};
    //             even.pop_back();
    //         }
    //     }
    //     if (even.empty()) break;
    // }

    // for(int x = 2 * n + 2; x <= k; x += 2){
    //     for(int j = 1; j <= n; j++){
    //         if ()
    //     }
    // }
    // for(int i = 1; i <= n && cur < k; i++){
    //     for(int j = 1; j <= n && cur < k; j++){
    //         if (!s.contains({i, j})){
    //             ans[++cur] = {i, j};
    //         }
    //     }
    // }
    // for(int i = 1; i <= n; i++){
        // assert(g1[i] == g2[i]);
    // }
    for(int i = 1; i <= k; i++){
        cout << ans[i].first << ' ' << ans[i].second << '\n';
    }


}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3484kb

input:

3 6

output:

1 3
2 3
1 1
2 2
3 1
3 2

result:

ok The answer is correct.

Test #2:

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

input:

3 7

output:

1 3
2 3
1 1
2 2
3 1
3 2
3 3

result:

ok The answer is correct.

Test #3:

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

input:

2 4

output:

1 1
1 2
2 2
2 1

result:

ok The answer is correct.

Test #4:

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

input:

3 9

output:

1 3
2 3
1 1
2 2
3 1
3 2
1 2
3 3
2 1

result:

ok The answer is correct.

Test #5:

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

input:

10 20

output:

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

result:

ok The answer is correct.

Test #6:

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

input:

10 100

output:

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

result:

ok The answer is correct.

Test #7:

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

input:

32 64

output:

1 1
1 2
2 2
2 1
3 5
4 5
3 3
4 4
5 3
5 4
6 8
7 8
6 6
7 7
8 6
8 7
9 11
10 11
9 9
10 10
11 9
11 10
12 14
13 14
12 12
13 13
14 12
14 13
15 17
16 17
15 15
16 16
17 15
17 16
18 20
19 20
18 18
19 19
20 18
20 19
21 23
22 23
21 21
22 22
23 21
23 22
24 26
25 26
24 24
25 25
26 24
26 25
27 29
28 29
27 27
28 28
...

result:

ok The answer is correct.

Test #8:

score: 0
Accepted
time: 89ms
memory: 28032kb

input:

200000 400000

output:

1 1
1 2
2 2
2 1
3 5
4 5
3 3
4 4
5 3
5 4
6 8
7 8
6 6
7 7
8 6
8 7
9 11
10 11
9 9
10 10
11 9
11 10
12 14
13 14
12 12
13 13
14 12
14 13
15 17
16 17
15 15
16 16
17 15
17 16
18 20
19 20
18 18
19 19
20 18
20 19
21 23
22 23
21 21
22 22
23 21
23 22
24 26
25 26
24 24
25 25
26 24
26 25
27 29
28 29
27 27
28 28
...

result:

ok The answer is correct.

Test #9:

score: 0
Accepted
time: 223ms
memory: 47996kb

input:

200000 745589

output:

1 1
1 2
2 2
2 1
3 5
4 5
3 3
4 4
5 3
5 4
6 8
7 8
6 6
7 7
8 6
8 7
9 11
10 11
9 9
10 10
11 9
11 10
12 14
13 14
12 12
13 13
14 12
14 13
15 17
16 17
15 15
16 16
17 15
17 16
18 20
19 20
18 18
19 19
20 18
20 19
21 23
22 23
21 21
22 22
23 21
23 22
24 26
25 26
24 24
25 25
26 24
26 25
27 29
28 29
27 27
28 28
...

result:

ok The answer is correct.

Test #10:

score: 0
Accepted
time: 276ms
memory: 62120kb

input:

199999 978736

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #11:

score: 0
Accepted
time: 168ms
memory: 40244kb

input:

198054 619549

output:

1 3
2 3
1 1
2 2
3 1
3 2
4 6
5 6
4 4
5 5
6 4
6 5
7 9
8 9
7 7
8 8
9 7
9 8
10 12
11 12
10 10
11 11
12 10
12 11
13 15
14 15
13 13
14 14
15 13
15 14
16 18
17 18
16 16
17 17
18 16
18 17
19 21
20 21
19 19
20 20
21 19
21 20
22 24
23 24
22 22
23 23
24 22
24 23
25 27
26 27
25 25
26 26
27 25
27 26
28 30
29 30
...

result:

ok The answer is correct.

Test #12:

score: 0
Accepted
time: 157ms
memory: 37500kb

input:

123124 567865

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #13:

score: 0
Accepted
time: 106ms
memory: 28164kb

input:

124252 416756

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #14:

score: 0
Accepted
time: 233ms
memory: 48316kb

input:

103503 748077

output:

1 3
2 3
1 1
2 2
3 1
3 2
4 6
5 6
4 4
5 5
6 4
6 5
7 9
8 9
7 7
8 8
9 7
9 8
10 12
11 12
10 10
11 11
12 10
12 11
13 15
14 15
13 13
14 14
15 13
15 14
16 18
17 18
16 16
17 17
18 16
18 17
19 21
20 21
19 19
20 20
21 19
21 20
22 24
23 24
22 22
23 23
24 22
24 23
25 27
26 27
25 25
26 26
27 25
27 26
28 30
29 30
...

result:

ok The answer is correct.

Test #15:

score: 0
Accepted
time: 315ms
memory: 62780kb

input:

120394 987331

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #16:

score: 0
Accepted
time: 186ms
memory: 40504kb

input:

123942 619710

output:

1 3
2 3
1 1
2 2
3 1
3 2
4 6
5 6
4 4
5 5
6 4
6 5
7 9
8 9
7 7
8 8
9 7
9 8
10 12
11 12
10 10
11 11
12 10
12 11
13 15
14 15
13 13
14 14
15 13
15 14
16 18
17 18
16 16
17 17
18 16
18 17
19 21
20 21
19 19
20 20
21 19
21 20
22 24
23 24
22 22
23 23
24 22
24 23
25 27
26 27
25 25
26 26
27 25
27 26
28 30
29 30
...

result:

ok The answer is correct.

Test #17:

score: 0
Accepted
time: 309ms
memory: 63636kb

input:

51251 1000000

output:

1 1
1 2
2 2
2 1
3 5
4 5
3 3
4 4
5 3
5 4
6 8
7 8
6 6
7 7
8 6
8 7
9 11
10 11
9 9
10 10
11 9
11 10
12 14
13 14
12 12
13 13
14 12
14 13
15 17
16 17
15 15
16 16
17 15
17 16
18 20
19 20
18 18
19 19
20 18
20 19
21 23
22 23
21 21
22 22
23 21
23 22
24 26
25 26
24 24
25 25
26 24
26 25
27 29
28 29
27 27
28 28
...

result:

ok The answer is correct.

Test #18:

score: 0
Accepted
time: 92ms
memory: 27968kb

input:

200000 400001

output:

1 1
1 2
2 2
2 1
3 5
4 5
3 3
4 4
5 3
5 4
6 8
7 8
6 6
7 7
8 6
8 7
9 11
10 11
9 9
10 10
11 9
11 10
12 14
13 14
12 12
13 13
14 12
14 13
15 17
16 17
15 15
16 16
17 15
17 16
18 20
19 20
18 18
19 19
20 18
20 19
21 23
22 23
21 21
22 22
23 21
23 22
24 26
25 26
24 24
25 25
26 24
26 25
27 29
28 29
27 27
28 28
...

result:

ok The answer is correct.

Test #19:

score: 0
Accepted
time: 84ms
memory: 27948kb

input:

199999 400001

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #20:

score: 0
Accepted
time: 42ms
memory: 15780kb

input:

100000 200000

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #21:

score: 0
Accepted
time: 6ms
memory: 5136kb

input:

14125 28290

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #22:

score: 0
Accepted
time: 314ms
memory: 63328kb

input:

200000 1000000

output:

1 1
1 2
2 2
2 1
3 5
4 5
3 3
4 4
5 3
5 4
6 8
7 8
6 6
7 7
8 6
8 7
9 11
10 11
9 9
10 10
11 9
11 10
12 14
13 14
12 12
13 13
14 12
14 13
15 17
16 17
15 15
16 16
17 15
17 16
18 20
19 20
18 18
19 19
20 18
20 19
21 23
22 23
21 21
22 22
23 21
23 22
24 26
25 26
24 24
25 25
26 24
26 25
27 29
28 29
27 27
28 28
...

result:

ok The answer is correct.

Test #23:

score: 0
Accepted
time: 312ms
memory: 63612kb

input:

100000 1000000

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #24:

score: 0
Accepted
time: 280ms
memory: 63808kb

input:

1000 1000000

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #25:

score: 0
Accepted
time: 69ms
memory: 20208kb

input:

532 283024

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #26:

score: 0
Accepted
time: 166ms
memory: 37452kb

input:

121434 568983

output:

1 3
2 3
1 1
2 2
3 1
3 2
4 6
5 6
4 4
5 5
6 4
6 5
7 9
8 9
7 7
8 8
9 7
9 8
10 12
11 12
10 10
11 11
12 10
12 11
13 15
14 15
13 13
14 14
15 13
15 14
16 18
17 18
16 16
17 17
18 16
18 17
19 21
20 21
19 19
20 20
21 19
21 20
22 24
23 24
22 22
23 23
24 22
24 23
25 27
26 27
25 25
26 26
27 25
27 26
28 30
29 30
...

result:

ok The answer is correct.

Test #27:

score: 0
Accepted
time: 7ms
memory: 5272kb

input:

11111 32222

output:

1 1
1 2
2 2
2 1
3 5
4 5
3 3
4 4
5 3
5 4
6 8
7 8
6 6
7 7
8 6
8 7
9 11
10 11
9 9
10 10
11 9
11 10
12 14
13 14
12 12
13 13
14 12
14 13
15 17
16 17
15 15
16 16
17 15
17 16
18 20
19 20
18 18
19 19
20 18
20 19
21 23
22 23
21 21
22 22
23 21
23 22
24 26
25 26
24 24
25 25
26 24
26 25
27 29
28 29
27 27
28 28
...

result:

ok The answer is correct.

Test #28:

score: 0
Accepted
time: 151ms
memory: 39348kb

input:

200000 600000

output:

1 1
1 2
2 2
2 1
3 5
4 5
3 3
4 4
5 3
5 4
6 8
7 8
6 6
7 7
8 6
8 7
9 11
10 11
9 9
10 10
11 9
11 10
12 14
13 14
12 12
13 13
14 12
14 13
15 17
16 17
15 15
16 16
17 15
17 16
18 20
19 20
18 18
19 19
20 18
20 19
21 23
22 23
21 21
22 22
23 21
23 22
24 26
25 26
24 24
25 25
26 24
26 25
27 29
28 29
27 27
28 28
...

result:

ok The answer is correct.

Test #29:

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

input:

64 128

output:

1 1
1 2
2 2
2 1
3 3
3 4
4 4
4 3
5 7
6 7
5 5
6 6
7 5
7 6
8 10
9 10
8 8
9 9
10 8
10 9
11 13
12 13
11 11
12 12
13 11
13 12
14 16
15 16
14 14
15 15
16 14
16 15
17 19
18 19
17 17
18 18
19 17
19 18
20 22
21 22
20 20
21 21
22 20
22 21
23 25
24 25
23 23
24 24
25 23
25 24
26 28
27 28
26 26
27 27
28 26
28 27
...

result:

ok The answer is correct.

Test #30:

score: 0
Accepted
time: 3ms
memory: 3988kb

input:

128 8920

output:

1 1
1 2
2 2
2 1
3 5
4 5
3 3
4 4
5 3
5 4
6 8
7 8
6 6
7 7
8 6
8 7
9 11
10 11
9 9
10 10
11 9
11 10
12 14
13 14
12 12
13 13
14 12
14 13
15 17
16 17
15 15
16 16
17 15
17 16
18 20
19 20
18 18
19 19
20 18
20 19
21 23
22 23
21 21
22 22
23 21
23 22
24 26
25 26
24 24
25 25
26 24
26 25
27 29
28 29
27 27
28 28
...

result:

ok The answer is correct.

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-03 07:33:06 | OpenSource Project