usaco_1_4_wormholes

usaco_1_4_wormholes.cpp

//
// Created by alice on 11/06/19.
// USACO 1.4 Wormholes
// AC
//
/*
ID: raining5
PROG: wormhole
LANG: C++
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include <bits/stdc++.h>

typedef long long LL;
using namespace std;

const string kProgName = "wormhole";

struct Position {
    LL x;
    LL y;
};

class Solver {
public:
    Solver () {
        ifstream f_in (kProgName + ".in");
        f_in >> n_;
        cd_.resize(n_);
        LL x, y;
        unordered_map<LL, vector<pair<LL, int>>> lines;
        for (int i = 0; i < n_; ++i) {
            f_in >> x >> y;
            wormholes_.push_back({x, y});
            cd_[i] = i;
            lines[wormholes_[i].y].push_back({x, i});
        }
        for (auto it = lines.begin(); it != lines.end(); ++it) {
            auto value = it -> second;
            y = it -> first;
            sort(value.begin(), value.end());
            lines_[y] = {};
            coord_[y].clear();
            for (int i = 0; i < value.size(); ++i) {
                lines_[y].push_back(value[i].second);
                coord_[y][value[i].second] = i;
            }
        }
#ifdef DEBUG
        cout << "n:" << n_ << " wormholes:" << endl;
        for (auto pos : wormholes_) {
            cout << pos.x << " " << pos.y << endl;
        }
        PrintPairs();
        cout << "\n\nlines (y: [wormhole_id]):" << endl;
        for (auto& pa: lines_) {
            cout << pa.first << ":";
            for (auto i: pa.second) {
                cout << " " << i;
            }
            cout << endl;
        }
        cout << "coord (y: [wormhole_id:pos]):" << endl;
        for (auto pa : coord_) {
            cout << pa.first << ":";
            for (auto pa2 : pa.second) {
                cout << " " << pa2.first << ":" << pa2.second;
            }
            cout << endl;
        }
        cout << endl;
#endif
    }

    void PrintPairs() {
        cout << "Pairs:" << endl;
        for (int i = 0; i < n_; i += 2) {
            cout << "[" << cd_[i] << " " << cd_[i + 1] << "] ";
        }
        cout << endl;
    }

    bool AreLineNeighbours(int u, int v) {
        return wormholes_[u].y == wormholes_[v].y &&
               abs(coord_[wormholes_[v].y][u] -
                   coord_[wormholes_[v].y][v]) == 1;
    }

    int CountUntrappedPairSets(int m) {
        if (m == n_) {
            return CycleExists() ? 0 : 1;
        }
        int count = 0;
        for (int i = m + 1; i < n_; ++i) {
            if (!AreLineNeighbours(cd_[m], cd_[i])) {
                swap(cd_[m + 1], cd_[i]);
                count += CountUntrappedPairSets(m + 2);
                swap(cd_[m + 1], cd_[i]);
            }
        }
        return count;
    }

    bool CycleExists() {
        vector<int> pairs(n_);
        for (int i = 0; i < n_; i += 2) {
            pairs[cd_[i]] = cd_[i + 1];
            pairs[cd_[i + 1]] = cd_[i];
        }
        // Check all start points
        int i_next_hole;
        for (int i = 0; i < n_; ++i) {
            i_next_hole = i;
            while (true) {
                i_next_hole = NextWormholeStart(i_next_hole);
                if (i_next_hole == -1) { break; }
                i_next_hole = pairs[i_next_hole];
                if (i_next_hole == i) { return true; }
            }
        }
        return false;
    }

    int NextWormholeStart(int i) {
        int i_next_pos = coord_[wormholes_[i].y][i] + 1;
        if (i_next_pos == lines_[wormholes_[i].y].size()) {
            // If i is the last hole on the line, then continue the +x won't
            // meet any other hole
            return -1;
        } else {
            return lines_[wormholes_[i].y][i_next_pos];
        }

    }

    int Run() {
        // if all worm holes are at different y levels
        if (all_of(lines_.cbegin(), lines_.cend(),
                [](const pair<const LL, vector<int>> &item) {
                    return item.second.size() == 1;
        })) {
            return 0;
        }
        int n_total = 1;
        // Simulate the selection process, the 0-th element can pick (n - 1) for
        // the 1st place, the 2nd element can pick (n - 3) for the 3rd place
        for (int i = n_ - 1; i > 0; i = i - 2)
            n_total *= i;
        return n_total - CountUntrappedPairSets(0);
    }

private:
    int n_;
    vector<Position> wormholes_;

    vector<int> cd_; // candidates pairs
    // For each **horizontal** line, key = y, value is a vector of wormhole id
    // arranged in increasing order of their x
    unordered_map<LL, vector<int>> lines_;
    // Given y and wormhole_id, return its position on lines_[y]
    unordered_map<LL, unordered_map<int, int>> coord_;
};

int main() {
    auto solver = Solver();
    ofstream f_out (kProgName + ".out");
    auto ans = solver.Run();
#ifdef DEBUG
    cout << "ans=" << ans << endl;
#endif
    f_out << ans << endl;
    return 0;
}