#include "permgame.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) { assert(m == 4); vector<vector<int>> adjList(m); vector<int> deg(m, 0); for(int i = 0; i < e; i++){ adjList[u[i]].push_back(v[i]); adjList[v[i]].push_back(u[i]); deg[u[i]]++; deg[v[i]]++; } // cout << "got degree\n"; bool isLoop = true; for(int i = 0; i < m; i++){ if(deg[i] > 2) isLoop = false; } // cout << "confirmed line " << end << '\n'; vector<int> line; if(isLoop){ int end = 0; line.push_back(end); int prev = -1; while(true){ int next = end; for(const int &x : adjList[end]){ if(x != prev) next = x; } if(next == 0) break; line.push_back(next); prev = end; end = next; } } // cout << "line: "; // for(int i = 0; i < line.size(); i++) cout << line[i] << ' '; // cout << '\n'; while(true && isLoop){ // cout << "in loop\n"; vector<bool> found(n, false); vector<vector<int>> cycles; int cycleTotal = 0; for(int i = 0; i < n; i++){ // cout << "checking: " << i << '\n'; if(found[i]) continue; found[i] = true; if(i == p[i]) continue; vector<int> cycle; cycle.push_back(i); int index = i; while(p[index] != i){ index = p[index]; cycle.push_back(index); found[index] = true; } // cout << "found cycle: "; // for(const auto &x : cycle) cout << x << ", "; // cout << '\n'; cycleTotal += cycle.size(); cycles.push_back(cycle); } // cout << "cycles: "; // for(int i = 0; i < cycles.size(); i++) cout << cycles[i].size() << ' '; // cout << '\n'; if(cycleTotal < line.size()) break; sort(cycles.begin(), cycles.end(), [](const vector<int> &a, const vector<int> &b){ return a.size() > b.size(); }); vector<vector<int>> cycle2; vector<vector<int>> cycle3; for(int i = 0; i < cycles.size(); i++){ if(cycles[i].size() == 2) cycle2.push_back(cycles[i]); if(cycles[i].size() == 3) cycle3.push_back(cycles[i]); } vector<int> t(line.size()); // cout << "t: "; if(cycles[0].size() >= m){ vector<int> cycle = cycles[0]; if(cycle.size() % 2 == 1 || cycle.size() == 4){ for(int i = 0; i < line.size(); i++){ t[line[i]] = cycle[i]; } }else{ assert(cycle.size() >= 6); for(int i = 0; i < line.size()-1; i++){ t[line[i]] = cycle[i]; } t[line[line.size()-1]] = cycle[4]; } }else{ if(line.size() <= cycle2.size() * 2){ int cycleI = 0; int cycleO = 0; for(int i = 0; i < line.size(); i++){ if(i - cycleO >= cycle2[cycleI].size()){ cycleO += cycle2[cycleI].size(); cycleI++; } t[line[i]] = cycle2[cycleI][i-cycleO]; // cout << t[i] << ' '; } }else if(line.size() <= cycle3.size() * 3){ int cycleI = 0; int cycleO = 0; for(int i = 0; i < line.size(); i++){ if(i - cycleO >= cycle3[cycleI].size()){ cycleO += cycle3[cycleI].size(); cycleI++; } t[line[i]] = cycle3[cycleI][i-cycleO]; // cout << t[i] << ' '; } }else{ // cout << "exiting\n"; break; } } // cout << '\n'; int j = Bob(t); swap(p[t[u[j]]], p[t[v[j]]]); } int score = 0; for(int i = 0; i < n; i++){ if(i == p[i]) score++; } return score; }