QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#541 | #334095 | #6537. One, Two, Three | December456 | December456 | Failed. | 2024-02-21 08:54:46 | 2024-02-21 08:54:46 |
Details
Extra Test:
Accepted
time: 1ms
memory: 9684kb
input:
23 3 3 1 3 1 2 2 2 3 2 3 2 1 1 2 1 3 2 1 3 3 1 2
output:
7 2 5 10 0 6 15 4 7 16 1 9 18 12 14 19 13 17 20 3 11 21
result:
ok count=7
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334095 | #6537. One, Two, Three | December456 | AC ✓ | 41ms | 19860kb | C++14 | 2.4kb | 2024-02-21 08:53:20 | 2024-02-21 08:53:21 |
answer
#include <algorithm>
#include <cstdio>
constexpr int maxn = 600000 + 2;
int a[maxn], c2[maxn], l1[maxn], l3[maxn];
int pos1[maxn], pos3[maxn], r1[maxn], r3[maxn];
void read(int& x) {
char ch;
while ((ch = getchar()) == '\n' && ch == ' ');
x = ch - '0';
while ((ch = getchar()) != '\n' && ch != ' ' && ch != EOF) {
x = (x << 1) + (x << 3) + ch - '0';
}
}
int main() {
int n, pt1 = 0, pt3 = 0;
read(n);
for (int i = 1; i <= n; i ++) {
read(a[i]);
c2[i] = c2[i - 1] + (a[i] == 2);
if (a[i] == 1) {
pos1[++ pt1] = i;
}
if (a[i] == 3) {
pos3[++ pt3] = i;
}
r1[i] = pt1;
r3[i] = pt3;
}
int c1 = pt1, c3 = pt3;
for (int i = n; i; i --) {
l1[i] = (a[i] == 1 ? -- pt1 : pt1) + 1;
l3[i] = (a[i] == 3 ? -- pt3 : pt3) + 1;
}
int x = c3, y = c1;
for (int i = 1; i <= x; i ++) {
while (x >= i && pos1[i] > pos3[c3 - x + i]) {
x --;
}
}
for (int i = 1; i <= y; i ++) {
while (y >= i && pos3[i] > pos1[c1 - y + i]) {
y --;
}
}
int ans = std::min(c1, c3), mn[3] = {n, n, n};
for (int i = 1; i <= n; i ++) {
mn[0] = std::min(mn[0], l1[i] - c2[i - 1]);
mn[1] = std::min(mn[1], l3[i] - c2[i - 1]);
mn[2] = std::min(mn[2], l1[i] + l3[i] - c2[i - 1]);
int t1 = c3 - r3[i] - 1, t2 = c1 - r1[i] - 1;
x = std::min(x, c2[i] + mn[0] + t1);
y = std::min(y, c2[i] + mn[1] + t2);
ans = std::min(ans, c2[i] + mn[2] + t1 + t2);
}
printf("%d\n", ans = std::min(ans, x + y));
y = ans - x;
int i1 = 0, i3 = 0;
pt1 = pt3 = 1;
while (pt1 <= x || pt3 <= y) {
if (pt3 > y || (pt1 <= x &&
pos3[c3 - x + pt1] < pos1[c1 - y + pt3])) {
i1 = std::max(i1, pos1[pt1] - 1);
while (a[++ i1] != 2);
a[i1] = 0;
printf("%d %d %d\n", pos1[pt1] - 1,
i1 - 1, pos3[c3 - x + pt1] - 1);
pt1 ++;
} else {
i3 = std::max(i3, pos3[pt3] - 1);
while (a[++ i3] != 2);
a[i3] = 0;
printf("%d %d %d\n", pos3[pt3] - 1,
i3 - 1, pos1[c1 - y + pt3] - 1);
pt3 ++;
}
}
return 0;
}