QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#541#334095#6537. One, Two, ThreeDecember456December456Failed.2024-02-21 08:54:462024-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

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334095#6537. One, Two, ThreeDecember456AC ✓41ms19860kbC++142.4kb2024-02-21 08:53:202024-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;
}