QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#209402 | #6320. Parallel Processing (Hard) | ucup-team870 | AC ✓ | 27ms | 4824kb | C++17 | 2.6kb | 2023-10-10 14:52:35 | 2023-10-10 14:52:35 |
Judging History
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