The Thing - BIO 2024 Round 2

/**
 * @file thing.cpp
 * @version 1.0
 * @date 2024-03-30
 *
 * usage:
 *      Read from / write to default input.txt and output.txt
 *          thing.exe
 *      Read from / write to custom files:
 *          thing.exe in.txt out.txt
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <set>
#include <cassert>

using namespace std;

void fileIO(int argc, char *argv[]);

const int n = 1024; // n*n grid; solution assumes n is not very small (e.g. n > 10)

bitset<n+1> grid[n+1]; // adding ones to allow overflows without errors
int countParity[2];
set<pair<int, int>> sorted[2];
set<pair<int, int>> movedAway;

inline void add(int x, int y) {
    grid[x][y] = true;
    sorted[(x+y)&1].emplace(x, y);
    ++countParity[(x+y)&1];
}
inline void remove(int x, int y) {
    grid[x][y] = false;
    sorted[(x+y)&1].erase({x, y});
    --countParity[(x+y)&1];
    if (movedAway.count({x, y})) movedAway.erase({x, y});
}
inline void annihilate(int x, int y, bool inX) {
    assert(grid[x][y]);
    remove(x, y);
    if (inX) {
        assert(grid[x+1][y]);
        remove(x+1, y);
        cout << "H " << x << ' ' << y << '\n';
    } else {
        assert(grid[x][y+1]);
        remove(x, y+1);
        cout << "V " << x << ' ' << y+1 << '\n';
    }
}
inline void annihilate(int x1, int y1, int x2, int y2) {
    assert(abs(x1-x2) + abs(y1-y2) == 1);
    annihilate(min(x1, x2), min(y1, y2), x1!=x2);
}
inline void clean() {
    // remove any adjacent pairs
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            if (grid[x][y]) {
                if (grid[x][y+1]) annihilate(x, y, false);
                else if (grid[x+1][y]) annihilate(x, y, true);
            }
        }
    }
}
inline void expand(int x, int y) {
    assert(0 < x && x+1 < n && 0 < y && y+1 < n && grid[x][y]);
    assert(!grid[x][y-1] && !grid[x-1][y] && !grid[x+1][y] && !grid[x][y+1]);
    remove(x, y);
    add(x-1, y), add(x, y-1), add(x+1, y), add(x, y+1);
    cout << "E " << x << ' ' << y << '\n';
}
inline bool canMoveTwo(int x, int y, int dx, int dy) {
    if (!grid[x][y] || grid[x+1][y] || grid[x][y+1] || grid[x][y-1] || grid[x-1][y]) return false;
    int x0 = x, y0 = y, x1 = x, y1 = y;
    if (dx) x0 += dx, x1 += dx, y0 -= 1, y1 += 1;
    else x0 -= 1, x1 += 1, y0 += dy, y1 += dy;
    if (grid[x0][y0] || grid[x1][y1] || grid[x+dx+dx][y+dy+dy]) return false;
    return true;
}
inline void moveTwo(int x, int y, int dx, int dy) {
    assert(canMoveTwo(x, y, dx, dy));
    expand(x, y);
    expand(x+dx, y+dy);
    annihilate(x, y, x-dx, y-dy);
    if (dx) {
        annihilate(x, y+1, x+dx, y+1);
        annihilate(x, y-1, x+dx, y-1);
    } else {
        annihilate(x+1, y, x+1, y+dy);
        annihilate(x-1, y, x-1, y+dy);
    }
}
inline bool comfortablyIn(int x, int y) {
    return x-2 >= 0 && y-2 >= 0 && x+2 < n && y+2 < n;
}
inline pair<int, int> occupiedSurrounding(int x, int y) {
    int x2 = x, y2 = y;
    if (grid[x-1][y]) x2-=1;
    else if (grid[x+1][y]) x2+=1;
    else if (grid[x][y-1]) y2-=1;
    else if (grid[x][y+1]) y2+=1;
    else x2 = -1, y2 = -1;
    return {x2, y2};
}
void cancelPair() {
    auto [xa, ya] = *prev(sorted[0].end());
    auto [xb, yb] = *prev(sorted[1].end());
    int a = 0, b = 1;
    if (make_pair(xa, ya) > make_pair(xb, yb)) {
        swap(a, b);
        swap(xa, xb);
        swap(ya, yb);
    }

    if (!movedAway.count({xb, yb})) {
        moveTwo(xb, yb, +1, 0); // separate (xb, yb) from the rest
        xb += 2;
        movedAway.emplace(xb, yb);
    }

    // move (xa, ya) towards (xb, yb)
    while (abs(xa-xb) + abs(ya-yb) > 1) {
        // move vertically first
        int dx = +1, dy = 0;
        if (xa >= xb-1) {
            dx = 0;
            dy = yb > ya ? +1 : -1;
        }
        if (canMoveTwo(xa, ya, dx, dy)) {
            moveTwo(xa, ya, dx, dy);
            xa += 2*dx, ya += 2*dy;
        } else {
            // none of the same colour should be in the way since we move vertically first
            // so there is a cell of opposite colour
            auto [xb2, yb2] = occupiedSurrounding(xa, ya);
            assert(xb2 != -1);
            // annihilate with that instead
            annihilate(xa, ya, xb2, yb2);
            break;
        }
    }
    if (grid[xa][ya]) annihilate(xa, ya, xb, yb);
}

int main(int argc, char *argv[]) {
    fileIO(argc, argv); // remove for standard input/output

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int c; cin >> c;
    for (int i = 0; i < c; ++i) {
        int x, y; cin >> x >> y;
        add(x, y);
    }
    int option = abs(countParity[0]-countParity[1]) % 5;
    cout << min(option, 5-option) << endl;
    clean();

    if ((!countParity[0] || !countParity[1]) && countParity[0] + countParity[1] <= 2) return 0;

    // move everything up once if they are not too close to the boundary
    set<pair<int, int>>::iterator it[2]{sorted[0].begin(), sorted[1].begin()};
    while (it[0] != sorted[0].end() || it[1] != sorted[1].end()) {
        int par = 1;
        if (it[1] == sorted[1].end() || (it[0] != sorted[0].end() && *it[0] < *it[1])) {
            par = 0;
        }
        auto [x, y] = *it[par];
        ++it[par];
        if (comfortablyIn(x-2, y) && canMoveTwo(x, y, -1, 0)) {
            moveTwo(x, y, -1, 0);
        }
    }

    // now the last four rows should be empty
    if (countParity[0]) assert(prev(sorted[0].end())->first < n-4);
    if (countParity[1]) assert(prev(sorted[1].end())->first < n-4);

    while ((countParity[0] && countParity[1]) || countParity[0] + countParity[1] > 2) {
        if (countParity[0] && countParity[1]) cancelPair();
        else {
            int a = sorted[0].empty() ? 1 : 0;
            auto [x, y] = *prev(sorted[a].end());
            expand(x, y);
        }
    }
    return 0;
}

void fileIO(int argc, char *argv[]) {
    const char * in = "input.txt", * out = "output.txt";
    if (argc > 1) in = argv[1];
    if (argc > 2) out = argv[2];
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
}