QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72458#5430. TriangeltalJerryTcl14 70ms9536kbC++14657b2023-01-15 17:26:412023-01-15 17:26:44

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 17:26:44]
  • 评测
  • 测评结果:14
  • 用时:70ms
  • 内存:9536kb
  • [2023-01-15 17:26:41]
  • 提交

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[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: 2ms
memory: 5608kb

input:

3
1 1 1

output:

YES
321

result:

ok Correct

Test #2:

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

input:

3
2 2 2

output:

NO

result:

ok Correct

Test #3:

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

input:

10
1 1 1 1 1 1 1 1 1 1

output:

YES
3333333321

result:

ok Correct

Test #4:

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

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

input:

10
4 4 4 4 4 4 4 4 4 4

output:

NO

result:

ok Correct

Test #6:

score: 0
Accepted
time: 14ms
memory: 8032kb

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: 62ms
memory: 9344kb

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: 65ms
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: 48ms
memory: 8524kb

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

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: 0ms
memory: 7556kb

input:

3
1 1 1

output:

YES
321

result:

ok Correct

Test #12:

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

input:

3
1 2 2

output:

NO

result:

ok Correct

Test #13:

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

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
333222111

result:

ok Correct

Test #14:

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

input:

10
2 3 1 4 3 1 4 3 4 2

output:

YES
3232231213

result:

ok Correct

Test #15:

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

input:

10
1 9 5 4 3 9 4 6 5 1

output:

NO

result:

ok Correct

Test #16:

score: 0
Accepted
time: 1ms
memory: 7588kb

input:

10
5 3 2 2 3 2 5 3 3 3

output:

YES
1233231222

result:

ok Correct

Test #17:

score: -16
Wrong Answer
time: 2ms
memory: 5476kb

input:

10
5 1 1 1 1 5 5 1 5 4

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: 2ms
memory: 7580kb

input:

4
1 1 1 1

output:

YES
3321

result:

ok Correct

Test #25:

score: 0
Accepted
time: 1ms
memory: 7584kb

input:

5
2 2 1 1 1

output:

YES
21332

result:

ok Correct

Test #26:

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

input:

3
3 1 1

output:

NO

result:

ok Correct

Test #27:

score: -11
Wrong Answer
time: 70ms
memory: 9340kb

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:

wrong answer Max of group 3 (3) 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%