QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209402#6320. Parallel Processing (Hard)ucup-team870AC ✓27ms4824kbC++172.6kb2023-10-10 14:52:352023-10-10 14:52:35

Judging History

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

  • [2023-10-10 14:52:35]
  • 评测
  • 测评结果:AC
  • 用时:27ms
  • 内存:4824kb
  • [2023-10-10 14:52:35]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
int a1[][3]={
{2,1,2},{4,3,4},{6,5,6},{8,7,8},
{3,2,3},{4,2,4},{7,6,7},{8,6,8},
{5,4,5},{6,4,6},{7,4,7},{8,4,8}
};
int a2[][3]={
{2,1,2},{4,3,4},{6,5,6},{9,8,9},
{3,2,3},{4,2,4},{7,6,7},{10,9,10},
{5,4,5},{6,4,6},{7,4,7},{11,10,11},
{8,7,8},{9,7,9},{10,7,10},{11,7,11}
};
int a3[][3]={
{2,1,2},{4,3,4},{6,5,6},{9,8,9},
{3,2,3},{4,2,4},{7,6,7},{10,9,10},
{5,4,5},{6,4,6},{7,4,7},{12,11,12},
{8,7,8},{9,7,9},{10,7,10},{13,12,13},
{11,10,11},{12,10,12},{13,10,13},{2000,2000,2000}
};
int a4[][3]={
{2,1,2},{4,3,4},{6,5,6},{8,7,8},
{3,2,3},{4,2,4},{9,8,9},{11,10,11},
{5,4,5},{6,4,6},{12,11,12},{14,13,14},
{7,6,7},{8,6,8},{9,6,9},{15,14,15},
{10,9,10},{11,9,11},{12,9,12},{16,15,16},
{13,12,13},{14,12,14},{15,12,15},{16,12,16}
};
int b[1005];
struct node{
    int x,y,z;
};
vector<node> v[1005];
queue<node> q[1005];
int main(){
    int n,ans,x,y,z; cin>>n; ans=n;
    For(i,1,500)
        For(j,1,333)
            For(k,0,250) if (i*2+j*3+k*4==n-2){
                int s=n-2-i-j-k;
                int c=n-1;
                if (!k) ++c;
                if ((i+j+k+1)*4>=s+c){
                    //cout<<i<<' '<<j<<' '<<k<<endl;
                    if ((i+j+k+1)<ans){
                        ans=i+j+k+1,x=i,y=j,z=k;
                    }
                }
            }
    printf("%d\n",ans);
    int cnt=1,l=3; b[2]=1; v[1].push_back(node{2,1,2});
    For(i,1,x){
        ++cnt;
        For(j,l,l+1) b[i]=cnt,v[cnt].push_back(node{j,l-1,j});
        q[cnt].push(node{l+1,l,l+1});
        l+=2;
    }
    For(i,1,y){
        ++cnt;
        For(j,l,l+2) b[i]=cnt,v[cnt].push_back(node{j,l-1,j});
        q[cnt].push(node{l+1,l,l+1}); q[cnt].push(node{l+2,l+1,l+2});
        l+=3;
    }
    For(i,1,z){
        ++cnt;
        For(j,l,l+3) b[i]=cnt,v[cnt].push_back(node{j,l-1,j});
        q[cnt].push(node{l+1,l,l+1}); q[cnt].push(node{l+2,l+1,l+2}); q[cnt].push(node{l+3,l+2,l+3});
        l+=4;
    }
    For(i,1,ans){
        for(auto o:v[i]) cout<<o.x<<' '<<o.y<<' '<<o.z<<endl;
        int cc=4-v[i].size(),xx=1;
        while(cc&&xx<=n){
            if (!q[xx].empty()){
                auto o=q[xx].front(); q[xx].pop();
                --cc;
                cout<<o.x<<' '<<o.y<<' '<<o.z<<endl;
            }
            ++xx;
        }
        if (cc){
            For(j,1,cc) cout<<2000<<' '<<2000<<' '<<2000<<endl;
        } 
    }
    //cout<<x<<' '<<y<<' '<<z<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 24ms
memory: 4452kb

input:

17

output:

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

result:

ok AC

Test #2:

score: 0
Accepted
time: 24ms
memory: 4456kb

input:

18

output:

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

result:

ok AC

Test #3:

score: 0
Accepted
time: 25ms
memory: 4500kb

input:

19

output:

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

result:

ok AC

Test #4:

score: 0
Accepted
time: 24ms
memory: 4448kb

input:

20

output:

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

result:

ok AC

Test #5:

score: 0
Accepted
time: 25ms
memory: 4496kb

input:

21

output:

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

result:

ok AC

Test #6:

score: 0
Accepted
time: 25ms
memory: 4436kb

input:

120

output:

48
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 19...

result:

ok AC

Test #7:

score: 0
Accepted
time: 25ms
memory: 4392kb

input:

421

output:

168
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 1...

result:

ok AC

Test #8:

score: 0
Accepted
time: 25ms
memory: 4508kb

input:

464

output:

186
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 1...

result:

ok AC

Test #9:

score: 0
Accepted
time: 26ms
memory: 4520kb

input:

812

output:

325
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 1...

result:

ok AC

Test #10:

score: 0
Accepted
time: 23ms
memory: 4424kb

input:

862

output:

345
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 1...

result:

ok AC

Test #11:

score: 0
Accepted
time: 26ms
memory: 4468kb

input:

996

output:

398
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 1...

result:

ok AC

Test #12:

score: 0
Accepted
time: 27ms
memory: 4500kb

input:

997

output:

399
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 1...

result:

ok AC

Test #13:

score: 0
Accepted
time: 26ms
memory: 4824kb

input:

998

output:

399
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 1...

result:

ok AC

Test #14:

score: 0
Accepted
time: 26ms
memory: 4756kb

input:

999

output:

400
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 1...

result:

ok AC

Test #15:

score: 0
Accepted
time: 23ms
memory: 4460kb

input:

1000

output:

400
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
10 9 10
12 11 12
5 4 5
6 4 6
14 13 14
16 15 16
7 6 7
8 6 8
18 17 18
20 19 20
9 8 9
10 8 10
22 21 22
24 23 24
11 10 11
12 10 12
26 25 26
28 27 28
13 12 13
14 12 14
30 29 30
32 31 32
15 14 15
16 14 16
34 33 34
36 35 36
17 16 17
18 16 18
38 37 38
40 39 40
19 18 1...

result:

ok AC