QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73053#5430. Triangeltal1234567850 45ms15068kbC++141.8kb2023-01-21 18:19:242023-01-21 18:19:26

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:19:26]
  • 评测
  • 测评结果:50
  • 用时:45ms
  • 内存:15068kb
  • [2023-01-21 18:19:24]
  • 提交

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 <= i && a[i].first <= j - i && a[j].first <= n - j) {
				for(int t = 1; t <= i; t++) ans[a[t].second] = 1;
				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] = 3;
				puts("YES");
				for(int t = 1; t <= n; t++) write(ans[t]);
				putchar('\n');
				return 0;
			}
		}
	}
	
	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

*/

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

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

input:

3
1 1 1

output:

YES
123

result:

ok Correct

Test #2:

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

input:

3
2 2 2

output:

NO

result:

ok Correct

Test #3:

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

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

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

input:

10
4 4 4 4 4 4 4 4 4 4

output:

NO

result:

ok Correct

Test #6:

score: 0
Accepted
time: 6ms
memory: 8140kb

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

result:

ok Correct

Test #7:

score: 0
Accepted
time: 23ms
memory: 14988kb

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

result:

ok Correct

Test #8:

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

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

result:

ok Correct

Test #9:

score: -14
Time Limit Exceeded

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:


result:


Subtask #2:

score: 16
Accepted

Test #11:

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

input:

3
1 1 1

output:

YES
123

result:

ok Correct

Test #12:

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

input:

3
1 2 2

output:

NO

result:

ok Correct

Test #13:

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

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

input:

10
2 3 1 4 3 1 4 3 4 2

output:

YES
1213213331

result:

ok Correct

Test #15:

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

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

input:

10
5 3 2 2 3 2 5 3 3 3

output:

YES
1233231222

result:

ok Correct

Test #17:

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

input:

10
5 1 1 1 1 5 5 1 5 4

output:

YES
3111133132

result:

ok Correct

Test #18:

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

input:

10
1 1 1 1 7 1 7 1 2 1

output:

YES
1111313121

result:

ok Correct

Test #19:

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

input:

10
3 3 3 2 5 3 2 5 2 2

output:

YES
2223123132

result:

ok Correct

Test #20:

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

input:

10
5 3 3 3 3 3 5 2 2 3

output:

NO

result:

ok Correct

Test #21:

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

input:

10
2 2 7 7 1 1 1 1 1 1

output:

NO

result:

ok Correct

Test #22:

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

input:

10
1 3 1 3 3 2 4 1 5 2

output:

YES
1212313131

result:

ok Correct

Test #23:

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

input:

3
1 2 2

output:

NO

result:

ok Correct

Subtask #3:

score: 11
Accepted

Test #24:

score: 11
Accepted
time: 2ms
memory: 5544kb

input:

4
1 1 1 1

output:

YES
1233

result:

ok Correct

Test #25:

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

input:

5
2 2 1 1 1

output:

YES
33112

result:

ok Correct

Test #26:

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

input:

3
3 1 1

output:

NO

result:

ok Correct

Test #27:

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

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

result:

ok Correct

Test #28:

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

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
111222333

result:

ok Correct

Test #29:

score: 0
Accepted
time: 13ms
memory: 14984kb

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

result:

ok Correct

Test #30:

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

input:

8
3 3 3 3 3 3 3 3

output:

NO

result:

ok Correct

Test #31:

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

input:

8
2 2 3 2 3 2 1 3

output:

YES
11323213

result:

ok Correct

Test #32:

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

input:

6
1 2 3 2 2 1

output:

YES
321223

result:

ok Correct

Test #33:

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

input:

6
1 3 2 3 1 1

output:

YES
132311

result:

ok Correct

Test #34:

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

input:

6
2 2 1 1 3 3

output:

NO

result:

ok Correct

Subtask #4:

score: 23
Accepted

Dependency #2:

100%
Accepted

Test #35:

score: 23
Accepted
time: 6ms
memory: 5368kb

input:

3000
946 211 1053 111 456 1294 810 1329 967 1198 256 1323 97 1318 109 1436 778 460 277 78 1345 190 13 183 340 557 504 1183 1190 1049 174 362 1304 1001 843 1065 453 605 472 1418 1046 1478 353 843 1024 723 656 1099 921 1102 604 959 1434 1294 1295 541 635 739 516 908 1445 1380 832 1293 62 43 82 879 70 ...

output:

NO

result:

ok Correct

Test #36:

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

input:

3000
30 556 623 1011 135 983 737 231 804 760 1071 646 296 540 689 934 410 391 393 488 200 830 396 592 154 605 880 400 368 653 1080 898 529 881 250 1088 325 881 877 38 482 435 265 426 351 569 1013 503 855 636 1073 363 307 81 322 59 457 240 923 101 551 359 614 546 283 353 849 519 424 793 574 918 412 6...

output:

YES
13331331333312332112131313321333231313312212133233311111213131331132233323233333333333321331112323333323311231131333111311131121233132331123131133333221313133112113133233323111133123111331132113131331321333311313313133333333311232223233131121313321323213312331332313133331112333332222211313311111...

result:

ok Correct

Test #37:

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

input:

3000
1936 2558 2469 2070 19 603 1655 1032 2508 75 1532 1671 209 2848 338 2834 2846 205 2895 1944 480 1394 1867 265 1473 1032 1332 1979 77 551 2748 185 1609 1762 1507 1972 1684 2605 396 2722 486 1967 670 2018 2934 2015 2215 308 911 604 1788 15 203 2772 2449 2791 2458 2100 1055 2862 740 258 1343 2672 ...

output:

NO

result:

ok Correct

Test #38:

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

input:

3000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...

output:

YES
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok Correct

Test #39:

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

input:

3000
500 1000 500 500 1000 500 1000 1000 1500 1000 1000 1000 1000 500 1500 1000 1000 1500 1000 500 1000 1000 1500 1000 500 1000 1000 1000 500 1000 1500 1000 1000 1000 1000 1000 1000 500 1000 1000 1000 500 1500 500 500 1500 500 1000 1000 500 500 1000 500 1000 500 1500 1000 500 500 500 1500 1000 500 1...

output:

YES
32332322122223122123221232223212222223222313313223323231233312322223213232221233222213222222322221231323232123333221323223332121322222333231213222222122131122122313322321232222332323221121322123133123313122223233323232311222321213123222231223232233223322232323322232311122312132332231323133211313...

result:

ok Correct

Test #40:

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

input:

3000
1000 1500 1500 1000 1000 1000 500 500 500 1000 500 500 500 1500 1500 1000 1500 1500 1500 500 1500 1000 500 500 500 1500 1500 500 500 1000 1000 500 1000 1500 500 1500 1500 1000 500 500 1500 500 1500 500 1500 500 1500 500 1500 1000 500 500 500 500 1500 500 1000 500 1500 1000 1000 500 1500 500 100...

output:

YES
23322211121113323331321113311221231332113131313132111131213221312131111313333221133313121121311331112123133121131113232331211211111211333212311313313111311321233332111221322112111131133111121223111113111112313111131211132112331221112131313133112233333211321331211121121111331121331331111311123212...

result:

ok Correct

Test #41:

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

input:

3000
1500 500 500 1500 1000 1500 500 500 1000 1500 1500 1000 500 1500 1500 1000 1500 500 500 1000 1500 1500 500 1000 1000 1000 500 1000 1500 500 1500 1000 1500 500 1500 1500 500 500 500 1500 1000 500 1500 500 500 500 500 1500 1500 500 1500 500 500 500 500 500 500 1500 500 1500 1500 1500 1000 1500 15...

output:

NO

result:

ok Correct

Test #42:

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

input:

3000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

YES
22222222222222222222222222222222222232222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

result:

ok Correct

Test #43:

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

input:

3000
1000 999 1001 1001 999 1001 999 999 1001 999 1000 999 1001 999 1000 1000 1000 1000 1001 1001 1001 999 1000 1000 1001 1001 1000 1000 1001 1000 1000 1000 1001 1001 1001 999 999 999 999 1001 1001 1001 1000 1000 999 1000 1001 999 999 1000 1000 999 999 999 1001 1001 1000 1000 1001 1001 1000 1001 100...

output:

YES
21331311312131222233312233223222333111133322123112211133223323211232311132221121322221113233113231221132131212122313331332213132232212313113121313313331113312232233112232331311133221213132223332332323232313322321132223231322332211331213332123131121213233213123332232112121321223311322323213213332...

result:

ok Correct

Test #44:

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

input:

3000
1000 999 999 999 1001 1000 1000 1000 999 999 1001 999 999 1001 999 1000 999 1001 999 1001 1001 1001 1000 1001 1001 1000 1000 999 999 999 1000 1000 999 1000 1001 1001 999 1001 1001 999 999 1001 1000 999 999 1001 1001 1001 1000 1000 999 999 1001 1000 1001 1001 1001 999 1000 1000 999 1001 1001 100...

output:

NO

result:

ok Correct

Test #45:

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

input:

3000
500 1500 500 500 1000 1500 500 1500 1500 500 500 500 500 500 500 1500 1500 1500 1000 500 500 500 500 1500 500 1000 1500 1500 500 1500 1500 1500 1000 1000 500 1500 499 1499 500 1500 1500 500 500 1500 500 500 1500 500 1500 500 1500 500 500 1000 1500 1000 500 1500 500 500 1500 1500 500 1500 1500 1...

output:

YES
13112313311111133321111312331333221313133113113131311232131133133323311313131111112111311322133311112132313111333132122331332132211213133313131132313211232123231312313332313311331133133133133311322131131111331111111311113212221233113123111221333111113311133311121131133331132213111121312331131112...

result:

ok Correct

Subtask #5:

score: 0
Skipped

Dependency #1:

0%