QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#426615	#6320. Parallel Processing (Hard)	james1BadCreeper	AC ✓	1ms	3676kb	C++17	4.7kb	2024-05-31 16:18:12	2024-05-31 16:18:14

Judging History

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

[2024-05-31 16:18:14]
评测

测评结果：AC
用时：1ms
内存：3676kb

查看

[2024-05-31 16:18:12]
提交

answer

#include <bits/stdc++.h>
using namespace std;

int id, n, I, be = 5; 
vector<tuple<int, int, int>> ans; 

/*
inline int get(int x) {
    if (x % 4 == 1) return x - 1; 
    if (x % 4 == 2) return x - 2; 
    if (x % 4 == 3) return x - 3; 
    return x - 4; 
}

int over = 4; 
inline void mkans(void) {
    if (get(be) <= over && be < I) {
        ans.emplace_back(be, get(be), be); 
        ++be; 
    } else ans.emplace_back(2000, 2000, 2000); 
}
*/

void solve(int n) {
    /*
    int I, be = 5; 
    for (I = 1; I + 3 - 1 <= n; I += 8) {
        ans.emplace_back(I + 1, I, I + 1); 
        if (I + 3 <= n) ans.emplace_back(I + 3, I + 2, I + 3); 
        else mkans(); 
        if (I + 1 + 4 <= n) ans.emplace_back(I + 1 + 4, I + 4, I + 1 + 4); 
        else mkans(); 
        if (I + 3 + 4 <= n) ans.emplace_back(I + 3 + 4, I + 2 + 4, I + 3 + 4); 
        else mkans(); 
        over = be; 

        ans.emplace_back(I + 2, I + 1, I + 2);  
        if (I + 3 <= n) ans.emplace_back(I + 3, I + 1, I + 3);  
        else mkans(); 
        if (I + 2 + 4 <= n) ans.emplace_back(I + 2 + 4, I + 1 + 4, I + 2 + 4); 
        else mkans(); 
        if (I + 3 + 4 <= n) ans.emplace_back(I + 3 + 4, I + 1 + 4, I + 3 + 4); 
        else mkans(); 
        over = be; 
    }
    if (I < n) {
        ans.emplace_back(I + 1, I, I + 1); 
        mkans(); mkans(); mkans(); over = be; 
    }
    // cerr << ans.size() << "\n"; 
    int cnt = 0; 
    while (be % 4 != 1) ans.emplace_back(be, get(be), be), ++be, ++cnt; 
    while (cnt != 0 && cnt != 4) ans.emplace_back(2000, 2000, 2000), ++cnt; 
    for (; be <= n; be += 4) {
        ans.emplace_back(be, get(be), be); 
        if (be + 1 <= n) ans.emplace_back(be + 1, get(be + 1), be + 1);  
        else ans.emplace_back(2000, 2000, 2000); 
        if (be + 2 <= n) ans.emplace_back(be + 2, get(be + 2), be + 2); 
        else ans.emplace_back(2000, 2000, 2000); 
        if (be + 3 <= n) ans.emplace_back(be + 3, get(be + 3), be + 3); 
        else ans.emplace_back(2000, 2000, 2000); 
    }
    */

    if (n >= 17) {
        solve(n - 10); // n - 9 
        auto add = [&](int a, int b, int c) -> void {
            if (a > n || b > n || c > n) ans.emplace_back(2000, 2000, 2000); 
            else ans.emplace_back(a + n - 11, b + n - 11, c + n - 11); 
        };
        add(2, 1, 2); add(4, 3, 4); add(6, 5, 6); add(8, 7, 8); 
        add(10, 9, 10); add(3, 2, 3); add(4, 2, 4); add(8, 6, 8); 
        add(5, 4, 5); add(6, 4, 6); add(8, 4, 8); add(11, 10, 11); 
        add(7, 6, 7); add(9, 8, 9); add(10, 8, 10); add(11, 8, 11);
        return; 
    }

    auto add = [&](int a, int b, int c) -> void {
        if (a > n || b > n || c > n) ans.emplace_back(2000, 2000, 2000);
        else ans.emplace_back(a, b, c);
    };
    if (n == 1) ;
    else if (n == 2) {
        add(2, 1, 2); add(2000, 2000, 2000); add(2000, 2000, 2000); add(2000, 2000, 2000);
    } else if (n <= 4) {
        add(2, 1, 2); add(4, 3, 4); add(2000, 2000, 2000); add(2000, 2000, 2000); 
        add(3, 2, 3); add(4, 2, 4); add(2000, 2000, 2000); add(2000, 2000, 2000);
    } else if (n <= 8) { 
        add(2, 1, 2); add(4, 3, 4); add(6, 5, 6); add(8, 7, 8); 
        add(3, 2, 3); add(4, 2, 4); add(7, 6, 7); add(8, 6, 8); 
        add(5, 4, 5); add(6, 4, 6); add(7, 4, 7); add(8, 4, 8);
    } else if (n <= 11) {
        add(2, 1, 2); add(4, 3, 4); add(6, 5, 6); add(8, 7, 8); 
        add(10, 9, 10); add(3, 2, 3); add(4, 2, 4); add(8, 6, 8); 
        add(5, 4, 5); add(6, 4, 6); add(8, 4, 8); add(11, 10, 11); 
        add(7, 6, 7); add(9, 8, 9); add(10, 8, 10); add(11, 8, 11);
    } else if (n <= 13) {
        add(2, 1, 2); add(4, 3, 4); add(6, 5, 6); add(8, 7, 8); 
        add(4, 2, 4); add(8, 6, 8); add(10, 9, 10); add(12, 11, 12);
        add(3, 2, 3); add(6, 4, 6); add(8, 4, 8); add(13, 12, 13); 
        add(5, 4, 5); add(7, 6, 7); add(9, 8, 9); add(10, 8, 10); 
        add(11, 10, 11); add(12, 10, 12); add(13, 10, 13); add(2000, 2000, 2000);
    } else if (n <= 16) {
        add(2, 1, 2); add(4, 3, 4); add(6, 5, 6); add(8, 7, 8); 
        add(4, 2, 4); add(8, 6, 8); add(10, 9, 10); add(12, 11, 12); 
        add(6, 4, 6); add(8, 4, 8); add(14, 13, 14); add(16, 15, 16); 
        add(3, 2, 3); add(5, 4, 5); add(10, 8, 10); add(14, 12, 14); 
        add(7, 6, 7); add(9, 8, 9); add(12, 10, 12); add(14, 10, 14); 
        add(11, 10, 11); add(13, 12, 13); add(15, 14, 15); add(16, 14, 16);
    }
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0); 
    cin >> n; 
    solve(n); 
    // cin >> n; 
    cout << ans.size() / 4 << "\n"; 
    for (auto [i, j, k] : ans) cout << i << " " << j << " " << k << "\n"; 
    return 0; 
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3624kb

input:

output:

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

result:

ok AC

Test #2:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

output:

result:

ok AC

Test #3:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

output:

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

result:

ok AC

Test #4:

score: 0

Accepted

time: 0ms

memory: 3520kb

input:

output:

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

result:

ok AC

Test #5:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

output:

result:

ok AC

Test #6:

score: 0

Accepted

time: 0ms

memory: 3544kb

input:

output:

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

result:

ok AC

Test #7:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

output:

result:

ok AC

Test #8:

score: 0

Accepted

time: 0ms

memory: 3652kb

input:

output:

186
2 1 2
4 3 4
6 5 6
8 7 8
4 2 4
8 6 8
10 9 10
12 11 12
6 4 6
8 4 8
14 13 14
2000 2000 2000
3 2 3
5 4 5
10 8 10
14 12 14
7 6 7
9 8 9
12 10 12
14 10 14
11 10 11
13 12 13
2000 2000 2000
2000 2000 2000
15 14 15
17 16 17
19 18 19
21 20 21
23 22 23
16 15 16
17 15 17
21 19 21
18 17 18
19 17 19
21 17 21
2...

result:

ok AC

Test #9:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

output:

325
2 1 2
4 3 4
6 5 6
8 7 8
4 2 4
8 6 8
10 9 10
12 11 12
3 2 3
6 4 6
8 4 8
2000 2000 2000
5 4 5
7 6 7
9 8 9
10 8 10
11 10 11
12 10 12
2000 2000 2000
2000 2000 2000
13 12 13
15 14 15
17 16 17
19 18 19
21 20 21
14 13 14
15 13 15
19 17 19
16 15 16
17 15 17
19 15 19
22 21 22
18 17 18
20 19 20
21 19 21
2...

result:

ok AC

Test #10:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

output:

345
2 1 2
4 3 4
6 5 6
8 7 8
4 2 4
8 6 8
10 9 10
12 11 12
3 2 3
6 4 6
8 4 8
2000 2000 2000
5 4 5
7 6 7
9 8 9
10 8 10
11 10 11
12 10 12
2000 2000 2000
2000 2000 2000
13 12 13
15 14 15
17 16 17
19 18 19
21 20 21
14 13 14
15 13 15
19 17 19
16 15 16
17 15 17
19 15 19
22 21 22
18 17 18
20 19 20
21 19 21
2...

result:

ok AC

Test #11:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

output:

result:

ok AC

Test #12:

score: 0

Accepted

time: 1ms

memory: 3656kb

input:

output:

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

result:

ok AC

Test #13:

score: 0

Accepted

time: 1ms

memory: 3676kb

input:

output:

result:

ok AC

Test #14:

score: 0

Accepted

time: 1ms

memory: 3648kb

input:

output:

400
2 1 2
4 3 4
6 5 6
8 7 8
2000 2000 2000
3 2 3
4 2 4
8 6 8
5 4 5
6 4 6
8 4 8
2000 2000 2000
7 6 7
9 8 9
2000 2000 2000
2000 2000 2000
10 9 10
12 11 12
14 13 14
16 15 16
18 17 18
11 10 11
12 10 12
16 14 16
13 12 13
14 12 14
16 12 16
19 18 19
15 14 15
17 16 17
18 16 18
19 16 19
20 19 20
22 21 22
24 ...

result:

ok AC

Test #15:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

output:

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

result:

ok AC