Submission #1204844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204844		model_code	Permutation Game (APIO25_permgame)	C++20	100 / 100	59 ms	584 KiB

permgame

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

#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << endl

#define vi vector<int>
#define vvi vector<vector<int>>
#define zz(x) x.insert(x.begin(),0);

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int n,m;
int arr[405];

vector<int> al[405];
ii edges[405];

vi chain; //this might be line or cycle

vvi cycs;

int decomp(){
	bool vis[405]={};
	cycs.clear();
	
	rep(x,0,n) if (!vis[x]){
		vi cyc={x};
		while (!vis[cyc.back()]){
			vis[cyc.back()]=true;
			cyc.pub(arr[cyc.back()]);
		}
		cyc.pob();
		cycs.pub(cyc);
	}
	
	sort(all(cycs),[](vi a,vi b){
		return sz(a)>sz(b);
	});
	
	int res=n;
	while (!cycs.empty() && sz(cycs.back())==1){
		res--;
		cycs.pob();
	}
	
	return res;
}

void send(vector<int> v){
	//v is in natural sorted order
	//we need to reshuffle it based on chain
	
	vi move(m);
	rep(x,0,m) move[chain[x]]=v[x];
	int idx=Bob(move);
	swap(arr[move[edges[idx].fi]],arr[move[edges[idx].se]]);
}

void splitOdd(vector<int> v){
	//split an odd cycle of size s>m into [2,s-2] or [1,s-1]
	
	vi res;
	for (int x=0;x<m;x+=2) res.pub(v[x]);
	for (int x=m-2;x>0;x-=2) res.pub(v[x]);
	send(res); 
}

void splitEven(vector<int> v){
	//split an even cycle of size s>=m+2 into [m,s-m] or [1,s-1]
	int s=sz(v);
	
	int curr=0;
	vi res={curr};
	rep(x,0,m/2-1){
		if (curr%(2*(s-m)-2)==0) curr+=s-m;
		else curr++;
		res.pub(curr);
	}
	
	curr++;
	res.pub(curr);
	
	curr-=(s-m);
	res.pub(curr);
	
	rep(x,0,m/2-2){
		if (curr%(2*(s-m)-2)==1) curr-=s-m;
		else curr--;
		res.pub(curr);
	}
	
	for (auto &it:res) it=v[it];
	
	send(res);
}

int Alice(int M, int E, vector<int> U, vector<int> V, int N, vector<int> P){
	n=N,m=M;
	
	rep(x,0,n) arr[x]=P[x];
	
	if (m==2){ //annoying case
		decomp();
		for (auto cyc:cycs) rep(x,1,sz(cyc)) Bob({cyc[0],cyc[x]});
		return n;
	}
	
	rep(x,0,E){
		al[U[x]].pub(V[x]);
		al[V[x]].pub(U[x]);
		edges[x]={U[x],V[x]};
	}
	
	int ans=0;
	rep(x,0,n) ans+=(arr[x]==x);
	
	bool bad=ans>=n-m+1;
	rep(x,0,m) if (sz(al[x])>=3) bad=true;
	
	if (bad) return ans;
	
	int r=0;
	rep(x,0,m) if (sz(al[x])==1) r=x;
	chain={r};
	rep(x,0,m-1){
		for (auto it:al[chain.back()]){
			if (sz(chain)==1 || chain[sz(chain)-2]!=it){
				chain.pub(it);
				break;
			}
		}
	}
	
    if (E+1==m || (m%2==0 && ans==n-m)){ //line graph or even cycle special case
		while (decomp()>=m){
			vi v;
			for (auto cyc:cycs) v.insert(v.end(),all(cyc));
			v.resize(m);
			send(v);
		}
		return n-m+1;
	}
	else if (m%2==1){ //odd cycle
		int goal=n-decomp();
		int odd=0,sz=0,ext=0;
		for (auto cyc:cycs){
			if (sz(cyc)%2==1) odd++;
			else sz+=sz(cyc);
		}
		
		for (auto cyc:cycs){
			if (sz(cyc)%2==1 && sz<m){
				ext++;
				sz+=sz(cyc);
			}
		}
		
		goal+=odd-2*(ext/2);
		
		while (decomp()>n-goal){
			vi v;
			
			//if ther is a big odd cycle, do opearation on them
			for (auto cyc:cycs) if (sz(cyc)%2==1){
				if (sz(cyc)>m){
					splitOdd(cyc);
					goto _done;
				}
				if (sz(cyc)==m){
					send(cyc);
					goto _done;;
				}
			}
			
			//there are no big odd cycles, we should try to combine cycles now
			for (auto cyc:cycs) if (sz(cyc)%2==0) v.insert(v.end(),all(cyc));
			while (sz(v)>m-1) v.pob(); //leave space for the odd cycle
			for (auto cyc:cycs) if (sz(cyc)%2==1) v.insert(v.end(),all(cyc));
			v.resize(m);
			send(v);
			
			_done:;
		}
		
		return goal;
	}
	else{ //even cycle
		while (decomp()>m+1){ //phase 1
			int tot=0;
			vi v;
			
			for (auto cyc:cycs) if (sz(cyc)==m){
				send(cyc);
				goto _done2;
			}
			
			for (auto cyc:cycs) if (sz(cyc)>=m+2){
				splitEven(cyc);
				goto _done2;
			}
			
			//try to combine cycles
			for (auto cyc:cycs) if (sz(cyc)>2) tot+=sz(cyc);
			
			if (tot<m+2) break; //end of phase 1
			
			for (auto cyc:cycs){
				v.insert(v.end(),all(cyc));
				//prevent the entire query being 1 cycle
				if (sz(v)==sz(cyc) && sz(v)>m-1) v.resize(m-1);
			}
			v.resize(m);
			send(v);
			
			_done2:;
		}
		
		while (decomp()>m+1){ //phase 2
			vi v;
			
			for (auto cyc:cycs) if (sz(cyc)==m){
				send(cyc);
				goto _done3;
			}
			
			for (auto cyc:cycs) if (sz(cyc)>=2*m-1){
				splitEven(cyc);
				goto _done3;
			}
			
			if (sz(cycs)==1) break; //end of phase 2
			
			for (auto cyc:cycs){
				v.insert(v.end(),all(cyc));
				//prevent the entire query being 1 cycle
				if (sz(v)==sz(cyc) && sz(v)>m-1) v.resize(m-1);
			}
			v.resize(m);
			send(v);
			
			_done3:;
		}
		
		while (decomp()>m+1){ //phase 3
			if (sz(cycs[0])==m) send(cycs[0]);
			else if (sz(cycs[0])>=m+2) splitEven(cycs[0]);
			else{
				vi v;
				for (auto cyc:cycs) v.insert(v.end(),all(cyc));
				v.resize(m);
				send(v);
			}
		}
		
		return n-m-1;
	}
}

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