QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#330208#6537. One, Two, Three08kevinWA 1ms4020kbC++142.0kb2024-02-17 13:41:352024-02-17 13:41:36

Judging History

你现在查看的是最新测评结果

  • [2024-02-17 13:41:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4020kb
  • [2024-02-17 13:41:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct node {
	ll x, y, z;
	bool friend operator < (node xx, node yy) {
		return xx.z > yy.z;
	}
} st1, st2;

ll n, ans, s1, s3;
ll a[500100];
ll t[10];
ll s[5][500100];
ll p[5][500100];
ll pos[10];
priority_queue<node> q;

int main() {
//	freopen("count.in", "r", stdin);
//	freopen("count.out", "w", stdout);
	scanf("%lld", &n);
	for (ll i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		s[a[i]][++t[a[i]]] = i;
	}
	pos[1] = pos[3] = 1;
	for (ll i = 1; i <= t[2]; i++) {
		ll x = s[2][i];
		while (pos[1] <= t[1] && s[1][pos[1]] <= x) {
			p[1][++s1] = s[1][pos[1]];
			pos[1]++;
		}
		while (pos[3] <= t[3] && s[3][pos[3]] <= x) {
			p[3][++s3] = s[3][pos[3]];
			pos[3]++;
		}
		if (s1 && pos[3] <= t[3] && !(s1 && pos[3] <= t[3] && s3 && pos[1] <= t[1] && s[3][pos[3]] > s[1][pos[1]])) {
			ans++;
			st1.x = p[1][s1];
			st1.y = x;
			st1.z = s[3][pos[3]];
			s1--;
			pos[3]++;
			q.push(st1);
			continue;
		}
		if (s3 && pos[1] <= t[1]) {
			ans++;
			st1.x = p[3][s3];
			st1.y = x;
			st1.z = s[1][pos[1]];
			s3--;
			pos[1]++;
			q.push(st1);
			continue;
		}
		if (ans && pos[1] < t[1] && pos[3] < t[3]) {
			st1 = q.top();
			if (st1.z <= x) {
				q.pop();
				if (a[st1.x] == 3) {
					ans++;
					st2.x = st1.z;
					st2.y = x;
					st2.z = s[3][pos[3]];
					st1.z = s[1][pos[1]];
				} else {
					ans++;
					st2.x = st1.z;
					st2.y = x;
					st2.z = s[1][pos[1]];
					st1.z = s[3][pos[3]];
				}
				q.push(st1);
				q.push(st2);
				pos[1]++;
				pos[3]++;
				continue;
			}
		}
		//~ cout << i << " " << s1 << " " << s3 << " " << pos[1] << " " << pos[3] << endl;
	}
	//~ cout << t[2] << endl;
	//~ cout << t[1] << " " << t[3] << endl;
	printf("%lld\n", ans);
	while (!q.empty()) {
		st1 = q.top();
		q.pop();
		printf("%lld %lld %lld\n", st1.x - 1, st1.y - 1, st1.z - 1);
	}
	//~ for (ll i = 1; i <= ans; i++) {
		//~ printf("%lld %lld %lld\n", d[i].x - 1, d[i].y - 1, d[i].z - 1);
	//~ }
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3888kb

input:

6
3 1 2 2 3 1

output:

2
1 2 4
0 3 5

result:

ok count=2

Test #2:

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

input:

6
2 1 3 1 3 2

output:

0

result:

ok count=0

Test #3:

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

input:

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

output:

499
13 14 15
11 18 19
9 20 21
24 27 28
26 29 31
23 30 32
22 39 40
45 46 47
48 51 52
8 54 55
5 60 61
66 67 72
70 71 77
78 79 80
83 84 85
86 87 88
81 92 93
96 97 98
95 99 117
104 105 119
112 113 120
125 128 129
133 138 139
143 144 145
146 148 149
151 162 163
164 167 169
132 168 170
171 176 177
180 181...

result:

ok count=499

Test #4:

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

input:

3000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

1
1373 1374 2901

result:

ok count=1

Test #5:

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

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

output:

1
1755 1756 1874

result:

ok count=1

Test #6:

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

input:

1500
1 1 1 2 1 1 1 2 2 2 2 2 1 1 3 1 2 2 3 1 2 2 2 2 1 2 1 2 1 1 3 1 2 2 2 2 1 1 3 1 1 2 2 3 2 1 3 1 1 2 2 2 1 2 2 2 2 2 1 2 3 2 3 2 3 2 1 3 2 1 2 3 2 2 3 2 3 1 1 3 1 3 1 3 3 3 1 3 3 3 1 1 3 1 3 1 3 1 1 1 3 1 3 1 3 3 1 1 1 3 1 1 3 1 1 1 1 1 3 3 3 3 1 3 1 1 1 1 3 3 3 3 3 3 1 3 1 1 1 3 1 3 1 1 1 1 3 1...

output:

500
24 25 76
46 55 77
18 23 78
26 27 79
38 50 80
31 32 81
30 35 82
28 33 83
29 34 84
5 8 85
60 61 86
40 41 87
36 42 88
37 44 89
62 63 90
64 65 91
48 49 92
43 53 93
4 9 94
67 70 95
39 51 96
14 22 97
71 73 98
74 75 99
1 10 100
45 54 102
0 11 104
47 56 105
52 57 109
58 59 112
15 16 118
13 17 119
19 20 ...

result:

ok count=500

Test #7:

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

input:

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

output:

1000
397 460 1775
833 1152 1776
55 226 1777
33 225 1778
835 1154 1779
400 463 1780
399 462 1781
837 1156 1782
822 1141 1783
402 464 1784
32 227 1785
839 1158 1786
824 1143 1787
51 229 1788
825 1144 1789
826 1145 1790
31 228 1791
403 465 1792
404 466 1793
830 1149 1794
49 230 1795
406 467 1796
843 11...

result:

ok count=1000

Test #8:

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

input:

3000
1 3 1 1 3 1 1 1 1 3 1 1 3 1 1 1 3 3 3 3 3 1 1 3 1 1 3 1 3 3 1 2 2 3 1 3 3 3 1 3 3 2 3 1 1 3 3 1 1 3 3 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 1 3 3 3 1 1 1 1 3 1 1 1 3 1 1 1 1 1 3 3 3 3 3 1 3 3 3 1 1 1 3 1 1 3 1 1 3 1 3 3 3 1 1 1 3 3 3 3 3 1 1 1...

output:

1000
318 340 1236
482 613 1237
160 220 1238
2 91 1239
615 660 1240
622 670 1241
623 671 1242
616 661 1243
617 663 1244
320 342 1245
322 343 1246
344 367 1247
0 92 1248
30 31 1249
156 224 1250
628 676 1251
629 677 1252
620 668 1253
630 678 1254
155 225 1255
621 669 1256
34 94 1257
38 41 1258
624 672 ...

result:

ok count=1000

Test #9:

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

input:

2997
3 1 2 2 1 1 1 1 1 1 3 1 3 3 1 3 3 3 1 3 1 2 1 1 3 1 2 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 3 3 1 1 3 1 3 1 1 3 3 1 3 1 3 3 3 1 1 1 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 1 3 1 1 1 1 1 3 3 3 1 3 1 1 3 3 3 1 3 3 1 1 1 3 1 1 3 1 1 3 2 3 3 3 2 3 2 3 1 2 1 1 3 1 1 3 2 2 2 2...

output:

999
229 241 432
230 242 433
68 93 434
231 243 435
5 44 436
4 45 437
196 216 438
232 244 439
197 217 440
198 218 441
113 157 442
234 246 443
200 219 444
1 3 445
235 247 446
114 158 447
237 249 448
10 46 449
116 160 450
204 221 451
22 47 452
117 161 453
255 257 454
60 85 455
259 287 456
206 223 457
20...

result:

ok count=999

Test #10:

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

input:

2994
1 1 2 1 2 1 2 2 3 1 3 3 3 3 1 3 1 1 2 3 3 1 3 3 3 3 1 1 1 3 3 2 3 1 3 1 3 3 1 2 3 1 3 3 3 1 3 1 3 2 3 2 1 1 3 1 1 1 3 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 3 1 1 2 3 3 3 3 3 3 1 3 1 3 1 1 2 1 3 3 3 2 2 3 2 1 3 3 3 1 2 1 1 2 3 3 1 3 2 2 2 2 2 2 2 2...

output:

998
767 977 1854
280 570 1855
768 978 1856
29 84 1857
810 1019 1858
811 1020 1859
769 979 1860
812 1021 1861
282 572 1862
770 980 1863
250 541 1864
772 982 1865
14 80 1866
774 984 1867
283 573 1868
252 543 1869
25 85 1870
816 1025 1871
776 986 1872
253 544 1873
254 545 1874
779 989 1875
285 575 1876...

result:

ok count=998

Test #11:

score: -100
Wrong Answer
time: 0ms
memory: 3996kb

input:

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

output:

999
354 377 392
353 378 394
335 380 396
334 383 398
332 386 399
128 139 400
142 391 401
387 389 402
140 390 404
138 141 408
145 393 409
148 395 410
127 144 411
143 147 412
32 146 413
149 397 414
152 403 416
153 405 417
31 150 419
20 151 421
137 154 423
155 156 424
162 415 426
164 165 428
167 170 430...

result:

wrong answer the number of matches is different