Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <algorithm>
- using std::cout;
- using std::endl;
- using std::vector;
- struct Point {
- int x;
- int y;
- };
- class Wormholes {
- private:
- const vector<Point>& wormholes;
- vector<int> to_the_right;
- vector<int> partners;
- public:
- Wormholes(const vector<Point>& wormholes)
- : wormholes(wormholes),
- to_the_right(wormholes.size(), -1),
- partners(wormholes.size(), -1) {
- for (int w = 0; w < wormholes.size(); w++) {
- vector<int> poss_next;
- for (int ow = 0; ow < wormholes.size(); ow++) {
- if (wormholes[w].y == wormholes[ow].y
- && wormholes[w].x < wormholes[ow].x) {
- poss_next.push_back(ow);
- }
- }
- std::sort(
- poss_next.begin(), poss_next.end(), [&] (int w1, int w2) {
- return wormholes[w1].x < wormholes[w2].x;
- });
- if (!poss_next.empty()) {
- to_the_right[w] = poss_next.front();
- }
- }
- }
- int count_valid() {
- // cout << partners << endl;
- bool all_paired = true;
- int w = 0;
- for (; w < wormholes.size(); w++) {
- if (partners[w] == -1) {
- all_paired = false;
- break;
- }
- }
- if (all_paired) {
- return inf_loop_possible();
- }
- int total = 0;
- for (int ow = w + 1; ow < wormholes.size(); ow++) {
- if (partners[ow] == -1) {
- partners[w] = ow;
- partners[ow] = w;
- total += count_valid();
- partners[w] = partners[ow] = -1;
- }
- }
- return total;
- }
- bool inf_loop_possible() {
- for (int s = 0; s < wormholes.size(); s++) {
- int pos = s;
- for (int i = 0; i < wormholes.size(); i++) {
- if (to_the_right[pos] == -1) {
- break;
- }
- pos = partners[to_the_right[pos]];
- if (pos == s) {
- return true;
- }
- }
- }
- return false;
- }
- };
- int main() {
- std::ifstream read("wormhole.in");
- int wormhole_num;
- read >> wormhole_num;
- vector<Point> wormholes(wormhole_num);
- for (Point& p : wormholes) {
- read >> p.x >> p.y;
- }
- std::ofstream("wormhole.out") << Wormholes(wormholes).count_valid() << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement