QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72559 | #5430. Triangeltal | JerryTcl | 14 | 59ms | 9688kb | C++14 | 1.1kb | 2023-01-16 15:45:29 | 2023-01-16 15:45:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;
int n, a[N], d[N], r[N];
int Get(int rk) { return a[d[rk]]; }
int main() {
scanf("%d", &n), iota(d + 1, d + 1 + n, 1);
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
sort(d + 1, d + 1 + n, [&](int x, int y) { return a[x] < a[y]; });
for(int mx2 = n - 1; mx2 >= 1; --mx2) {
if(Get(mx2) + Get(n) <= mx2) {
if(Get(Get(mx2)) + Get(mx2) + Get(n) > n) continue;
for(int i = mx2 + 1; i <= n; ++i) r[d[i]] = 1;
for(int i = mx2 - Get(n) + 1; i <= mx2; ++i) r[d[i]] = 2;
for(int i = Get(mx2) + 1; i <= mx2 - Get(n); ++i) r[d[i]] = 1;
for(int i = 1; i <= Get(mx2); ++i) r[d[i]] = 3;
} else if(Get(mx2) + Get(n) < n) {
int mx3 = Get(mx2) + Get(n);
if(Get(mx3) > n - mx3) continue;
for(int i = mx3 + 1; i <= n; ++i) r[d[i]] = 1;
for(int i = mx2 + 1; i <= mx3; ++i) r[d[i]] = 3;
for(int i = mx2 - Get(n) + 1; i <= mx2; ++i) r[d[i]] = 2;
for(int i = 1; i <= mx2 - Get(n); ++i) r[d[i]] = 3;
} else continue;
puts("YES"); for(int i = 1; i <= n; ++i) printf("%d", r[i]); return 0;
}
return puts("NO"), 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 14
Accepted
Test #1:
score: 14
Accepted
time: 3ms
memory: 7928kb
input:
3 1 1 1
output:
YES 321
result:
ok Correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 7628kb
input:
3 2 2 2
output:
NO
result:
ok Correct
Test #3:
score: 0
Accepted
time: 3ms
memory: 7676kb
input:
10 1 1 1 1 1 1 1 1 1 1
output:
YES 3111111121
result:
ok Correct
Test #4:
score: 0
Accepted
time: 2ms
memory: 7744kb
input:
10 3 3 3 3 3 3 3 3 3 3
output:
YES 3331112221
result:
ok Correct
Test #5:
score: 0
Accepted
time: 2ms
memory: 7796kb
input:
10 4 4 4 4 4 4 4 4 4 4
output:
NO
result:
ok Correct
Test #6:
score: 0
Accepted
time: 11ms
memory: 8288kb
input:
99999 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 ...
output:
YES 22222222222211111111111112222222222222222222222221111111111111111111111111111111111111111111111111222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct
Test #7:
score: 0
Accepted
time: 57ms
memory: 9688kb
input:
500000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
YES 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct
Test #8:
score: 0
Accepted
time: 58ms
memory: 9684kb
input:
500000 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666...
output:
YES 22222222222221111111111111111111222222222222222222222222222221111111111111111111111111111111111111111111111111111111111111222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222221111111111111111111111111111111111111111111111111111...
result:
ok Correct
Test #9:
score: 0
Accepted
time: 48ms
memory: 8476kb
input:
500000 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667...
output:
NO
result:
ok Correct
Test #10:
score: 0
Accepted
time: 31ms
memory: 8168kb
input:
500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000...
output:
NO
result:
ok Correct
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 16
Accepted
time: 3ms
memory: 5568kb
input:
3 1 1 1
output:
YES 321
result:
ok Correct
Test #12:
score: 0
Accepted
time: 2ms
memory: 7768kb
input:
3 1 2 2
output:
NO
result:
ok Correct
Test #13:
score: 0
Accepted
time: 3ms
memory: 7676kb
input:
9 3 3 3 3 3 3 3 3 3
output:
YES 333112221
result:
ok Correct
Test #14:
score: 0
Accepted
time: 2ms
memory: 7736kb
input:
10 2 3 1 4 3 1 4 3 4 2
output:
YES 3132232213
result:
ok Correct
Test #15:
score: 0
Accepted
time: 3ms
memory: 5376kb
input:
10 1 9 5 4 3 9 4 6 5 1
output:
NO
result:
ok Correct
Test #16:
score: 0
Accepted
time: 3ms
memory: 7776kb
input:
10 5 3 2 2 3 2 5 3 3 3
output:
YES 1233231222
result:
ok Correct
Test #17:
score: 0
Accepted
time: 3ms
memory: 7900kb
input:
10 5 1 1 1 1 5 5 1 5 4
output:
YES 1222211213
result:
ok Correct
Test #18:
score: 0
Accepted
time: 2ms
memory: 7732kb
input:
10 1 1 1 1 7 1 7 1 2 1
output:
YES 2222121232
result:
ok Correct
Test #19:
score: 0
Accepted
time: 3ms
memory: 7612kb
input:
10 3 3 3 2 5 3 2 5 2 2
output:
YES 2223123132
result:
ok Correct
Test #20:
score: -16
Wrong Answer
time: 3ms
memory: 7672kb
input:
10 5 3 3 3 3 3 5 2 2 3
output:
YES 1333331221
result:
wrong answer Max of group 1 (5) was bigger than size of the next group (2)
Subtask #3:
score: 0
Wrong Answer
Test #24:
score: 11
Accepted
time: 0ms
memory: 7728kb
input:
4 1 1 1 1
output:
YES 3121
result:
ok Correct
Test #25:
score: 0
Accepted
time: 0ms
memory: 7676kb
input:
5 2 2 1 1 1
output:
YES 21332
result:
ok Correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 7716kb
input:
3 3 1 1
output:
NO
result:
ok Correct
Test #27:
score: 0
Accepted
time: 59ms
memory: 9416kb
input:
500000 1 2 3 1 2 3 2 2 3 3 1 1 2 3 1 1 2 3 1 3 2 1 2 3 1 3 3 3 1 2 3 2 2 2 1 3 1 2 2 2 2 3 3 1 3 3 1 2 2 3 1 2 3 2 2 1 1 1 3 2 3 1 1 2 3 1 2 1 1 1 1 1 1 3 3 1 2 2 2 2 3 2 2 1 3 3 3 2 1 3 1 1 1 1 2 3 3 3 3 2 2 3 1 1 1 2 2 1 3 3 3 2 2 3 3 1 2 3 2 3 2 2 2 2 2 3 1 3 2 1 2 1 2 2 2 1 1 1 1 2 1 3 1 1 1 1 2...
output:
YES 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct
Test #28:
score: 0
Accepted
time: 3ms
memory: 7904kb
input:
9 3 3 3 3 3 3 3 3 3
output:
YES 333112221
result:
ok Correct
Test #29:
score: 0
Accepted
time: 58ms
memory: 9496kb
input:
500000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
YES 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct
Test #30:
score: 0
Accepted
time: 3ms
memory: 7596kb
input:
8 3 3 3 3 3 3 3 3
output:
NO
result:
ok Correct
Test #31:
score: 0
Accepted
time: 3ms
memory: 7924kb
input:
8 2 2 3 2 3 2 1 3
output:
YES 33212231
result:
ok Correct
Test #32:
score: 0
Accepted
time: 2ms
memory: 7740kb
input:
6 1 2 3 2 2 1
output:
YES 321223
result:
ok Correct
Test #33:
score: 0
Accepted
time: 0ms
memory: 7932kb
input:
6 1 3 2 3 1 1
output:
YES 213122
result:
ok Correct
Test #34:
score: -11
Wrong Answer
time: 2ms
memory: 5700kb
input:
6 2 2 1 1 3 3
output:
YES 332211
result:
wrong answer Max of group 1 (3) was bigger than size of the next group (2)
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%