QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#330208 | #6537. One, Two, Three | 08kevin | WA | 1ms | 4020kb | C++14 | 2.0kb | 2024-02-17 13:41:35 | 2024-02-17 13:41:36 |
Judging History
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;
}
详细
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