Submission #1205373

#TimeUsernameProblemLanguageResultExecution timeMemory
1205373MamedovPermutation Game (APIO25_permgame)C++20
22 / 100
13 ms536 KiB
#include "permgame.h" #include <bits/stdc++.h> #define vi vector<int> #define vll vector<ll> #define vvi vector<vi> #define oo 1000000001 #define eb emplace_back #define pb push_back #define mpr make_pair #define ln '\n' #define ull unsigned long long #define ll long long #define all(v) v.begin(), v.end() #define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> void show(vector<T> &v) { for (T i : v) { cout << i << ' '; } cout << ln; } int getScore(int n, vi &p) { int score = 0; for (int i = 0; i < n; ++i) { if (p[i] == i) ++score; } return score; } vvi getCycles(int n, vi &p) { vvi cycles; vi vis(n, 0); for (int i = 0; i < n; ++i) { vi cycle; if (!vis[i]) { int node = i; while (!vis[node]) { vis[node] = 1; cycle.eb(node); node = p[node]; } } cycles.eb(cycle); } sort(all(cycles), [&](vi &i, vi &j) {return i.size() > j.size();}); return cycles; } int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) { int curScore = getScore(n, p); vvi g(m); for (int i = 0; i < e; ++i) { g[u[i]].eb(v[i]); g[v[i]].eb(u[i]); } int a = -1; for (int i = 0; i < m; ++i) { if (g[i].size() > 2) return curScore; // can't improve if (g[i].size() == 1) a = i; // end of chain } vi ord; if (a == -1) a = 0; // cycle int b = -1; for (int i = 0; i < m; ++i) { ord.eb(a); int nxt = g[a][0]; if (nxt == b) nxt = g[i][1]; b = a; a = nxt; } int optimalScore; vi t(m); if (e == m - 1) { if (curScore >= n - (m - 1)) return curScore; optimalScore = n - (m - 1); if (m == 2) optimalScore = n; while (curScore < optimalScore) { vvi cycles = getCycles(n, p); int id = 0, pos = 0; for (int i = 0; i < m; ++i) { if (pos == size(cycles[id])) { pos = 0; ++id; } t[ord[i]] = cycles[id][pos++]; } int j = Bob(t); swap(p[t[u[j]]], p[t[v[j]]]); curScore = getScore(n, p); } } else if (m == 3) { vvi cycles = getCycles(n, p); //for (auto c : cycles) show(c); int oddCycles = 0; for (auto c : cycles) if (c.size() % 2 == 1) ++oddCycles; //cerr << "oddCycles = " << oddCycles << ln; optimalScore = oddCycles; int ops = 0; while (curScore < optimalScore) { vi oddCycle; for (auto c : cycles) if (c.size() % 2 == 1) { oddCycle = c; break; } for (int i = 0; i < m; ++i) { t[i] = oddCycle[ord[i]]; } int j = Bob(t); ++ops; assert(ops <= 3 * n); swap(p[t[u[j]]], p[t[v[j]]]); curScore = getScore(n, p); } } else if (m == 4) { if (curScore == n - 5 || curScore >= n - 3) return curScore; if (curScore == n - 4) optimalScore = n - 3; else optimalScore = n - 5; while (curScore < optimalScore) { vvi cycles = getCycles(n, p); int sz = cycles.size(); if (cycles[0].size() >= 4) { for (int i = 0; i < m; ++i) { t[ord[i]] = cycles[0][i]; } if (cycles[0].size() == 6) t[ord[m - 1]] = cycles[0][m]; } else { // merge two cycles of size = 3 or size = 2 if (cycles[0].size() == 3 && cycles[1].size() == 3) { for (int i = 0; i < m - 1; ++i) t[ord[i]] = cycles[0][i]; t[ord[m - 1]] = cycles[1][0]; } else { while (cycles[sz - 1].size() == 1) --sz; if (cycles[sz - 1].size() == 2 && cycles[sz - 2].size() == 2) { t[ord[0]] = cycles[sz - 1][0]; t[ord[1]] = cycles[sz - 1][1]; t[ord[2]] = cycles[sz - 2][0]; t[ord[3]] = cycles[sz - 2][1]; } else { assert(false); } } } int j = Bob(t); swap(p[t[u[j]]], p[t[v[j]]]); curScore = getScore(n, p); } } return optimalScore; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...