| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1248580 | yoyoyoxx | Permutation Game (APIO25_permgame) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int bob(vector<int> t); // provided
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[p[i]] = i;
}
int current = 0;
for (int i = 0; i < n; i++) {
if (p[i] == i) current++;
}
int k = n - m + 1;
if (current >= k) return current;
// Play to increase to k
// For general, we attempt to fix from high to low.
for (int k = n - 1; k >= 0; k--) {
if (p[k] == k) continue;
int b = pos[k];
// Construct t to swap v and b
vector<int> t(m, -1);
// Find an adjacent pair
int x = 0, y = 1; // assume vertices 0 and 1 are adjacent, general find one.
bool found = false;
for (int j = 0; j < e; j++) {
x = u[j];
y = v[j];
break;
}
t[x] = k;
t[y] = b;
// Fill other with distinct positions
set<int> used;
used.insert(k);
used.insert(b);
vector<int> available;
for (int i = 0; i < n; i++) {
if (used.count(i) == 0) available.push_back(i);
}
int idx = 0;
for (int z = 0; z < m; z++) {
if (t[z] == -1) {
t[z] = available[idx % available.size()];
idx++;
}
}
// Ensure distinct
set<int> check;
for (int z = 0; z < m; z++) {
if (check.count(t[z]) ) {
// if not distinct, adjust
// for simplicity, assume n large enough.
}
check.insert(t[z]);
}
// Call bob
int j = bob(t);
int p1 = t[u[j]];
int p2 = t[v[j]];
swap(p[p1], p[p2]);
swap(pos[p[p1]], pos[p[p2]]);
// Now, check current
current = 0;
for (int i = 0; i < n; i++) {
if (p[i] == i) current++;
}
if (current >= k) break;
}
return k;
}