Submission #1249810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249810		PlayVoltz	Permutation Game (APIO25_permgame)	C++20	46 / 100	17 ms	540 KiB

permgame

#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, m;
vector<int> p, chain;
vector<pii> edges;
vector<vector<int> > vect, graph;

bool custom(vector<int> a, vector<int> b){
	return a.size()>b.size();
}

int decomp(){
	vector<bool> visited(n, 0);
	vect.clear();
	for (int i=0; i<n; ++i)if (!visited[i]){
		vector<int> temp(1, i);
		visited[i]=1;
		while (!visited[p[temp.back()]])visited[p[temp.back()]]=1, temp.pb(p[temp.back()]);
		vect.pb(temp);
	}
	sort(vect.begin(), vect.end(), custom);
	int res=0;
	while (vect.size()&&vect.back().size()==1)++res, vect.pop_back();
	return n-res;
}

void bob(vector<int> temp){
	vector<int> res(m);
	for (int i=0; i<m; ++i)res[chain[i]]=temp[i];
	int id=Bob(res);
	swap(p[res[edges[id].fi]], p[res[edges[id].se]]);
}

void odd(vector<int> temp){
	vector<int> res;
	for (int i=0; i<m; i+=2)res.pb(temp[i]);
	for (int i=m-2; i>0; i-=2)res.pb(temp[i]);
	bob(res);
}

int Alice(int M, int e, vector<int> u, vector<int> v, int N, vector<int> P){
	n=N, m=M;
	p=P;
	graph.resize(n);
	if (m==2){
		decomp();
		for (auto c:vect)for (int i=1; i<c.size(); ++i)Bob({c[0], c[i]});
		return n;
	}
	edges.resize(e);
	for (int i=0; i<e; ++i){
		graph[u[i]].pb(v[i]);
		graph[v[i]].pb(u[i]);
		edges[i]=mp(u[i], v[i]);
	}
	int ans=0;
	bool die=0;
	for (int i=0; i<n; ++i)if (i==p[i])++ans;
	for (int i=0; i<n; ++i)if (graph[i].size()>=3)die=1;
	if (die||ans>=n-m+1)return ans;
	int start=0;
	for (int i=0; i<n; ++i)if (graph[i].size()==1)start=i;
	chain.resize(1, start);
	for (int i=1; i<m; ++i){
		if (chain.size()==1||graph[chain.back()][0]!=chain[chain.size()-2])chain.pb(graph[chain.back()][0]);
		else chain.pb(graph[chain.back()][1]);
	}
	if (e==m-1){
		while (decomp()>=m){
			vector<int> temp;
			for (auto c:vect)for (auto a:c)temp.pb(a);
			temp.resize(m);
			bob(temp);
		}
		return n-m+1;
	}
	if (m%2){
		int best=n-decomp(), o=0, sum=0, del=0;
		for (auto c:vect){
			if (c.size()%2)++o;
			else sum+=c.size();
		}
		for (auto c:vect)if (c.size()%2&&sum<m)sum+=c.size(), ++del;
		best+=o-del+del%2;
		while (decomp()>n-best){
			bool got=0;
			for (auto c:vect)if (c.size()%2){
				if (c.size()>m){
					odd(c);
					got=1;
					break;
				}
				if (c.size()==m){
					bob(c);
					got=1;
					break;
				}
			}
			if (!got){
				vector<int> temp;
				for (auto c:vect)if (!(c.size()%2))for (auto a:c)temp.pb(a);
				while (temp.size()>=m)temp.pop_back();
				for (auto c:vect)if (c.size()%2)for (auto a:c)temp.pb(a);
				temp.resize(m);
				bob(temp);
			}
		}
		return best;
	}
}

Compilation message (stderr)

permgame.cpp: In function 'int Alice(int, int, std::vector<int>, std::vector<int>, int, std::vector<int>)':
permgame.cpp:118:1: warning: control reaches end of non-void function [-Wreturn-type]
  118 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 24 / 24
• Subtask 5: 0 / 24
• Subtask 6: 0 / 30