QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73054#5430. Triangeltal123456780 1837ms15148kbC++141.4kb2023-01-21 18:23:192023-01-21 18:23:23

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-21 18:23:23]
  • 评测
  • 测评结果:0
  • 用时:1837ms
  • 内存:15148kb
  • [2023-01-21 18:23:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define inf 1e9
#define pii pair <int, int>
const int mod = 1e9 + 7;
inline int read () {
	int x = 0, f = 1;
	char ch = getchar ();
	while (ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar ();
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar ();
	return x * f;
}
inline void write (int x) {
	if (x < 0) x = -x, putchar ('-');
	if (x >= 10) write (x / 10);
	putchar (x % 10 + '0');
}
inline int quickmod (int x, int y) {
	int Ans = 1;
	while (y) {
		if (y & 1) Ans = (Ans * x) % mod;
		x = (x * x) % mod;
		y >>= 1;
	}
	return Ans;
}
int n;
pii a[500005];
int ans[500005];
signed main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; i++) a[i] = mp(read(), i);
	
	sort(a + 1, a + 1 + n);
	
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			if(a[n].first <= j - i && a[i].first <= n - j && a[j].first <= i) {
				for(int t = 1; t <= i; t++) ans[a[t].second] = 3;
				for(int t = i + 1; t <= j; t++) ans[a[t].second] = 2;
				for(int t = j + 1; t <= n; t++) ans[a[t].second] = 1;
				puts("YES");
				for(int t = 1; t <= n; t++) write(ans[t]);
				putchar('\n');
				return 0;
			}
		}
	}
	puts("NO");
	return 0;
}
/*
10
5 3 2 2 3 2 5 3 3 3

*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 14
Accepted
time: 2ms
memory: 5252kb

input:

3
1 1 1

output:

YES
321

result:

ok Correct

Test #2:

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

input:

3
2 2 2

output:

NO

result:

ok Correct

Test #3:

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

input:

10
1 1 1 1 1 1 1 1 1 1

output:

YES
3211111111

result:

ok Correct

Test #4:

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

input:

10
3 3 3 3 3 3 3 3 3 3

output:

YES
3332221111

result:

ok Correct

Test #5:

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

input:

10
4 4 4 4 4 4 4 4 4 4

output:

NO

result:

ok Correct

Test #6:

score: 0
Accepted
time: 1837ms
memory: 9880kb

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

result:

ok Correct

Test #7:

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

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

result:

ok Correct

Test #8:

score: -14
Time Limit Exceeded

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:


result:


Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 16
Accepted
time: 1ms
memory: 5324kb

input:

3
1 1 1

output:

YES
321

result:

ok Correct

Test #12:

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

input:

3
1 2 2

output:

NO

result:

ok Correct

Test #13:

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

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

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

input:

10
1 9 5 4 3 9 4 6 5 1

output:

NO

result:

ok Correct

Test #16:

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

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

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

input:

4
1 1 1 1

output:

YES
3211

result:

ok Correct

Test #25:

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

input:

5
2 2 1 1 1

output:

YES
11322

result:

ok Correct

Test #26:

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

input:

3
3 1 1

output:

NO

result:

ok Correct

Test #27:

score: 0
Accepted
time: 50ms
memory: 15148kb

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

result:

ok Correct

Test #28:

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

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
333222111

result:

ok Correct

Test #29:

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

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

result:

ok Correct

Test #30:

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

input:

8
3 3 3 3 3 3 3 3

output:

NO

result:

ok Correct

Test #31:

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

input:

8
2 2 3 2 3 2 1 3

output:

YES
32121231

result:

ok Correct

Test #32:

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

input:

6
1 2 3 2 2 1

output:

YES
321223

result:

ok Correct

Test #33:

score: -11
Wrong Answer
time: 2ms
memory: 5544kb

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:

0%