| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1235090 | Hanksburger | Permutation Game (APIO25_permgame) | C++20 | 0 ms | 0 KiB |
#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > perm;
vector<int> adj[405], vec;
int ans;
bool cmp(vector<int> &vec1, vector<int> &vec2)
{
if (vec1.size()==4)
return 1;
if (vec2.size()==4)
return 0;
return vec1.size()<vec2.size(); // beware of inequality direction
}
void computePerm(vector<int> P)
{
int visited[405]={};
ans=0;
perm.clear();
for (int i=0; i<P.size(); i++)
{
if (visited[i])
continue;
vector<int> tmp;
int cur=i;
while (!visited[cur])
{
tmp.push_back(cur);
visited[cur]=1;
cur=P[cur];
}
if (tmp.size()==1)
ans++;
else
perm.push_back(tmp);
}
sort(perm.begin(), perm.end(), cmp); // DONT FORGET THIS NEW ADDITION
}
int Alice(int M, int E, vector<int> U, vector<int> V, int N, vector<int> P)
{
for (int i=0; i<E; i++)
{
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
vec.push_back(0);
for (int i=1; i<M; i++)
{
if (i==1)
vec.push_back(adj[vec[i-1]][0]);
else
{
int pre=vec[i-2];
if (adj[vec[i-1]][0]==pre)
vec.push_back(adj[vec[i-1]][1]);
else
vec.push_back(adj[vec[i-1]][0]);
}
}
computePerm(P);
for (int i=0; i<M; i++)
if (adj[i].size()>=3)
return ans;
int optimal;
if (ans>=n-3)
return ans;
if (ans==n-4)
optimal=n-3;
else
optimal=n-5;
while (1)
{
int updated=0;
for (int i=0; i<perm.size(); i++)
{
if (perm[i].size()==4)
{
//cout << "here1\n";
updated=1;
vector<int> tmp(4);
tmp[vec[0]]=perm[i][0];
tmp[vec[1]]=perm[i][1];
tmp[vec[2]]=perm[i][2];
tmp[vec[3]]=perm[i][3];
int edge=Bob(tmp);
swap(P[tmp[U[edge]]], P[tmp[V[edge]]]);
computePerm(P);
break;
}
}
if (updated)
continue;
for (int i=0; i<perm.size(); i++)
{
if (perm[i].size()>4)
{
//cout << "here2\n";
updated=1;
vector<int> tmp(4);
tmp[vec[0]]=perm[i][0];
tmp[vec[1]]=perm[i][1];
tmp[vec[2]]=perm[i][2];
tmp[vec[3]]=perm[i][4];
int edge=Bob(tmp);
swap(P[tmp[U[edge]]], P[tmp[V[edge]]]);
computePerm(P);
break;
}
}
if (updated)
continue;
if (perm.size()>=2 && perm[0].size()==2 && perm[1].size()==2)
{
//cout << "here3\n";
updated=1;
vector<int> tmp(4);
tmp[vec[0]]=perm[0][0];
tmp[vec[1]]=perm[0][1];
tmp[vec[2]]=perm[1][0];
tmp[vec[3]]=perm[1][1];
int edge=Bob(tmp);
swap(P[tmp[U[edge]]], P[tmp[V[edge]]]);
computePerm(P);
continue;
}
if (perm.size()>=2 && perm[perm.size()-2].size()==3 && perm[perm.size()-1].size()==3)
{
//cout << "here4\n";
updated=1;
vector<int> tmp(4);
tmp[vec[0]]=perm[perm.size()-2][0];
tmp[vec[1]]=perm[perm.size()-2][1];
tmp[vec[2]]=perm[perm.size()-2][2];
tmp[vec[3]]=perm[perm.size()-1][0];
int edge=Bob(tmp);
swap(P[tmp[U[edge]]], P[tmp[V[edge]]]);
computePerm(P);
continue;
}
if (!updated)
break;
}
return optimal;
}