QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72457#5430. TriangeltalJerryTcl14 87ms9540kbC++14651b2023-01-15 16:48:482023-01-15 16:48:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-15 16:48:49]
  • 评测
  • 测评结果:14
  • 用时:87ms
  • 内存:9540kb
  • [2023-01-15 16:48:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n, a[500007], d[500007], r[500007], mx;
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 i = n; i >= 1; --i) {
		if(a[d[i - 1]] > n - i + 1) continue;
		if(a[d[n]] + a[d[i - 1]] > i - 1) continue;
		puts("YES");
		for(int j = i; j <= n; ++j) r[d[j]] = 1;
		for(int j = i - a[d[n]]; j < i; ++j) r[d[j]] = 2;
		for(int j = 1; j < i - a[d[n]]; ++j) r[d[j]] = 3;
		for(int j = 1; j <= n; ++j) printf("%d", r[j]);
		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: 0ms
memory: 7640kb

input:

3
1 1 1

output:

YES
321

result:

ok Correct

Test #2:

score: 0
Accepted
time: 2ms
memory: 7624kb

input:

3
2 2 2

output:

NO

result:

ok Correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 7748kb

input:

10
1 1 1 1 1 1 1 1 1 1

output:

YES
3333333321

result:

ok Correct

Test #4:

score: 0
Accepted
time: 3ms
memory: 7660kb

input:

10
3 3 3 3 3 3 3 3 3 3

output:

YES
3333222111

result:

ok Correct

Test #5:

score: 0
Accepted
time: 2ms
memory: 7524kb

input:

10
4 4 4 4 4 4 4 4 4 4

output:

NO

result:

ok Correct

Test #6:

score: 0
Accepted
time: 19ms
memory: 7988kb

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
11111111111122222222222222111111111111111111111112222222222222222222222222222222222222222222222222111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

result:

ok Correct

Test #7:

score: 0
Accepted
time: 64ms
memory: 9536kb

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
33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...

result:

ok Correct

Test #8:

score: 0
Accepted
time: 87ms
memory: 9536kb

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
11111111111122222222222222222222111111111111111111111111111112222222222222222222222222222222222222222222222222222222222222111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112222222222222222222222222222222222222222222222222222...

result:

ok Correct

Test #9:

score: 0
Accepted
time: 52ms
memory: 7444kb

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: 56ms
memory: 8572kb

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: 7596kb

input:

3
1 1 1

output:

YES
321

result:

ok Correct

Test #12:

score: 0
Accepted
time: 2ms
memory: 7400kb

input:

3
1 2 2

output:

NO

result:

ok Correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 7572kb

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
333222111

result:

ok Correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 7748kb

input:

10
2 3 1 4 3 1 4 3 4 2

output:

YES
3231231212

result:

ok Correct

Test #15:

score: 0
Accepted
time: 2ms
memory: 7472kb

input:

10
1 9 5 4 3 9 4 6 5 1

output:

NO

result:

ok Correct

Test #16:

score: -16
Wrong Answer
time: 3ms
memory: 7520kb

input:

10
5 3 2 2 3 2 5 3 3 3

output:

NO

result:

wrong answer Contestant said no, but judge found a solution

Subtask #3:

score: 0
Wrong Answer

Test #24:

score: 11
Accepted
time: 0ms
memory: 7664kb

input:

4
1 1 1 1

output:

YES
3321

result:

ok Correct

Test #25:

score: 0
Accepted
time: 3ms
memory: 7780kb

input:

5
2 2 1 1 1

output:

YES
11322

result:

ok Correct

Test #26:

score: 0
Accepted
time: 2ms
memory: 7516kb

input:

3
3 1 1

output:

NO

result:

ok Correct

Test #27:

score: 0
Accepted
time: 61ms
memory: 9364kb

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
33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...

result:

ok Correct

Test #28:

score: 0
Accepted
time: 2ms
memory: 7780kb

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
333222111

result:

ok Correct

Test #29:

score: 0
Accepted
time: 68ms
memory: 9540kb

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
33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...

result:

ok Correct

Test #30:

score: 0
Accepted
time: 3ms
memory: 7540kb

input:

8
3 3 3 3 3 3 3 3

output:

NO

result:

ok Correct

Test #31:

score: 0
Accepted
time: 3ms
memory: 7580kb

input:

8
2 2 3 2 3 2 1 3

output:

YES
32121231

result:

ok Correct

Test #32:

score: -11
Wrong Answer
time: 1ms
memory: 7620kb

input:

6
1 2 3 2 2 1

output:

NO

result:

wrong answer Contestant said no, but judge found a solution

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%