wormholes v2 AC

wormholes_v2.cpp

/*
ID: raining5
PROG: wormhole
LANG: C++
*/
// Version 2 after reading the solution
#include <bits/stdc++.h>
#define N_MAX 12

using namespace std;

const string kProgName = "wormhole";

int N, kNextRight[N_MAX];


class Solver {
public:
    Solver () {
        ifstream f_in (kProgName + ".in");
        f_in >> N;
        int x, y;

        unordered_map<int, vector<pair<int, int>>> lines;
        for (int i = 0; i < N; ++i) {
            f_in >> x >> y;
            lines[y].push_back({x, i});
        }

        for (auto& [y, x_and_id_list] : lines) {
            sort(x_and_id_list.begin(), x_and_id_list.end());
            for (int i = 1; i < x_and_id_list.size(); ++i) {
                kNextRight[x_and_id_list[i - 1].second] =
                        x_and_id_list[i].second;
            }
            kNextRight[x_and_id_list.back().second] = -1;
        }
        partners_.resize(N, -1);
    }

    int CountUnstuckPairSets() {
        int m = 0;
        while (m < N && partners_[m] != -1) {
            ++m;
        }
        if (m == N) {
            return CycleExists() ? 0 : 1;
        }
        int count = 0;
        // pair m with all i > m if i is not m's next right
        for (int i = m + 1; i < N; ++i) {
            if (partners_[i] == -1 && kNextRight[i] != m && kNextRight[m] != i) {
                partners_[i] = m;
                partners_[m] = i;
                count += CountUnstuckPairSets();
                partners_[m] = partners_[i] = -1;
            }
        }
        return count;
    }

    bool CycleExists() {
        int i_next_hole;
        for (int i = 0; i < N; ++i) {
            // Check when each hole as start
            i_next_hole = i;
            while (true) {
                i_next_hole = kNextRight[i_next_hole];
                if (i_next_hole == -1) { break; }
                i_next_hole = partners_[i_next_hole];
                if (i_next_hole == i) { return true; }
            }
        }
        return false;
    }

    int Run() {
        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 - CountUnstuckPairSets();
    }

private:
    vector<int> partners_;
};

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