QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72160#5430. TriangeltalGemini7X14 74ms9380kbC++14758b2023-01-14 17:35:502023-01-14 19:13:13

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-14 19:13:13]
  • 评测
  • 测评结果:14
  • 用时:74ms
  • 内存:9380kb
  • [2023-01-14 17:35:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int n, a[maxn], rk[maxn], ans[maxn];
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", a + i), rk[i] = i;
	sort(rk + 1, rk + 1 + n, [](int x, int y){
		return a[x] > a[y];
	});
	for (int i = 1, j = n + 1; i <= n; i++)
	{
		while (j > 1 && a[rk[j - 1]] <= i) j--;
		if (a[rk[i + 1]] <= n - (i + a[rk[1]]) && j <= i + a[rk[i]] + 1)
		{
			puts("YES");
			for (int j = 1; j <= i; j++) ans[rk[j]] = 1;
			for (int j = i + 1; j <= i + a[rk[1]]; j++) ans[rk[j]] = 2;
			for (int j = i + a[rk[1]] + 1; j <= n; j++) ans[rk[j]] = 3;
			for (int j = 1; j <= n; j++) printf("%d", ans[j]);
			puts("");
			return 0;
		}
	}
	puts("NO");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 14
Accepted

Test #1:

score: 14
Accepted
time: 1ms
memory: 3700kb

input:

3
1 1 1

output:

YES
123

result:

ok Correct

Test #2:

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

input:

3
2 2 2

output:

NO

result:

ok Correct

Test #3:

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

input:

10
1 1 1 1 1 1 1 1 1 1

output:

YES
1233333333

result:

ok Correct

Test #4:

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

input:

10
3 3 3 3 3 3 3 3 3 3

output:

YES
1112223333

result:

ok Correct

Test #5:

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

input:

10
4 4 4 4 4 4 4 4 4 4

output:

NO

result:

ok Correct

Test #6:

score: 0
Accepted
time: 18ms
memory: 4684kb

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

result:

ok Correct

Test #7:

score: 0
Accepted
time: 66ms
memory: 9352kb

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

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

result:

ok Correct

Test #9:

score: 0
Accepted
time: 53ms
memory: 7284kb

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: 43ms
memory: 7288kb

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

input:

3
1 1 1

output:

YES
123

result:

ok Correct

Test #12:

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

input:

3
1 2 2

output:

NO

result:

ok Correct

Test #13:

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

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
111222333

result:

ok Correct

Test #14:

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

input:

10
2 3 1 4 3 1 4 3 4 2

output:

YES
3231231223

result:

ok Correct

Test #15:

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

input:

10
1 9 5 4 3 9 4 6 5 1

output:

NO

result:

ok Correct

Test #16:

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

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

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

input:

4
1 1 1 1

output:

YES
1233

result:

ok Correct

Test #25:

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

input:

5
2 2 1 1 1

output:

YES
12233

result:

ok Correct

Test #26:

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

input:

3
3 1 1

output:

NO

result:

ok Correct

Test #27:

score: 0
Accepted
time: 66ms
memory: 9356kb

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

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
111222333

result:

ok Correct

Test #29:

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

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

input:

8
3 3 3 3 3 3 3 3

output:

NO

result:

ok Correct

Test #31:

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

input:

8
2 2 3 2 3 2 1 3

output:

YES
22131332

result:

ok Correct

Test #32:

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

input:

6
1 2 3 2 2 1

output:

YES
321223

result:

ok Correct

Test #33:

score: -11
Wrong Answer
time: 0ms
memory: 3368kb

input:

6
1 3 2 3 1 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%