QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72251 | #5430. Triangeltal | swift | 14 | 59ms | 9372kb | C++23 | 1.4kb | 2023-01-15 11:13:04 | 2023-01-15 11:13:04 |
Judging History
answer
#include <bits/stdc++.h>
#define N 510000
using namespace std;
int n, ans[N];
pair<int, int> a[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].first, a[i].second = i;
sort(a + 1, a + n + 1);
for (int i = 1; i < n; i++) {
if (i >= a[n].first && i + a[i].first < n &&
a[i + a[i].first].first <= n - (i + a[i].first)) {
for (int j = 1; j <= i; j++)
ans[a[j].second] = 1;
for (int j = i + 1; j <= i + a[i].first; j++)
ans[a[j].second] = 3;
for (int j = i + a[i].first + 1; j <= n; j++)
ans[a[j].second] = 2;
cout << "YES" << '\n';
for (int j = 1; j <= n; j++)
cout << ans[j];
cout << '\n';
exit(0);
} else {
int l = i + a[n].first,
r = min((int)(upper_bound(a + 1, a + n + 1, make_pair(i, n)) - a - 1),
n - a[i].first);
if (l <= r && l < n) {
for (int j = 1; j <= i; j++)
ans[a[j].second] = 1;
for (int j = i + 1; j <= l; j++)
ans[a[j].second] = 2;
for (int j = l + 1; j <= n; j++)
ans[a[j].second] = 3;
cout << "YES" << '\n';
for (int j = 1; j <= n; j++)
cout << ans[j];
cout << '\n';
exit(0);
}
}
}
cout << "NO" << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 14
Accepted
Test #1:
score: 14
Accepted
time: 2ms
memory: 5360kb
input:
3 1 1 1
output:
YES 132
result:
ok Correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 3500kb
input:
3 2 2 2
output:
NO
result:
ok Correct
Test #3:
score: 0
Accepted
time: 1ms
memory: 5584kb
input:
10 1 1 1 1 1 1 1 1 1 1
output:
YES 1322222222
result:
ok Correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 5444kb
input:
10 3 3 3 3 3 3 3 3 3 3
output:
YES 1113332222
result:
ok Correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3312kb
input:
10 4 4 4 4 4 4 4 4 4 4
output:
NO
result:
ok Correct
Test #6:
score: 0
Accepted
time: 16ms
memory: 7768kb
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 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct
Test #7:
score: 0
Accepted
time: 49ms
memory: 9372kb
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 13222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...
result:
ok Correct
Test #8:
score: 0
Accepted
time: 56ms
memory: 9320kb
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 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct
Test #9:
score: 0
Accepted
time: 59ms
memory: 7304kb
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: 47ms
memory: 7892kb
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: 2ms
memory: 5428kb
input:
3 1 1 1
output:
YES 132
result:
ok Correct
Test #12:
score: 0
Accepted
time: 1ms
memory: 3348kb
input:
3 1 2 2
output:
NO
result:
ok Correct
Test #13:
score: 0
Accepted
time: 2ms
memory: 5416kb
input:
9 3 3 3 3 3 3 3 3 3
output:
YES 111333222
result:
ok Correct
Test #14:
score: -16
Wrong Answer
time: 2ms
memory: 5380kb
input:
10 2 3 1 4 3 1 4 3 4 2
output:
YES 1213213232
result:
wrong answer Max of group 3 (4) was bigger than size of the next group (3)
Subtask #3:
score: 0
Wrong Answer
Test #24:
score: 11
Accepted
time: 2ms
memory: 5416kb
input:
4 1 1 1 1
output:
YES 1322
result:
ok Correct
Test #25:
score: -11
Wrong Answer
time: 1ms
memory: 5548kb
input:
5 2 2 1 1 1
output:
YES 33122
result:
wrong answer Max of group 3 (2) was bigger than size of the next group (1)
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%