QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72559#5430. TriangeltalJerryTcl14 59ms9688kbC++141.1kb2023-01-16 15:45:292023-01-16 15:45:32

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-16 15:45:32]
  • 评测
  • 测评结果:14
  • 用时:59ms
  • 内存:9688kb
  • [2023-01-16 15:45:29]
  • 提交

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;
}

詳細信息

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%