Submission #1205030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205030		irmuun	Permutation Game (APIO25_permgame)	C++20	36 / 100	23 ms	460 KiB

permgame

#include "permgame.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=400;

vector<int>g[N];//initial graph/not P
vector<bool>vis(N);
vector<int>line;
vector<vector<int>>f;
vector<int>t;
int ans=0;
vector<array<int,3>>d;
int m,e,n;
vector<int>u,v,p;
vector<int>opt;

void find(int x){
	line.pb(x);
	vis[x]=true;
	for(int y:g[x]){
		if(!vis[y]){
			find(y);
		}
	}
}

void dfs(int x){
	vis[x]=true;
	f.back().pb(x);
	for(int y:g[x]){
		if(!vis[y]){
			dfs(y);
		}
	}
}

void go(){
	fill(all(vis),false);
	for(int i=0;i<n;i++){
		g[i].clear();
	}
	f.clear();
	for(int i=0;i<n;i++){
		g[p[i]].pb(i);
		g[i].pb(p[i]);
	}
	for(int i=0;i<n;i++){
		if(!vis[i]){
			f.pb({});
			dfs(i);
		}
	}
	sort(all(f),[&](vector<int>a,vector<int>b){
		return (int)a.size()>(int)b.size();
	});
}

void solve3(){
	go();
	for(int i=0;i<f.size();i++){
		if(f[i].size()>=3&&opt[f[i].size()]>0){
			int sz=f[i].size();
			t[0]=f[i][d[sz][0]-1];
			t[1]=f[i][d[sz][0]+d[sz][1]-1];
			t[2]=f[i][d[sz][0]+d[sz][1]+d[sz][2]-1];
			int j=Bob(t);
			swap(p[t[u[j]]], p[t[v[j]]]);
			solve3();
			return;
		}
	}
	return;
}

int Alice(int M, int E, vector<int> U, vector<int> V, int N_, vector<int> P) {
	m=M,e=E,u=U,v=V,n=N_,p=P;
	t.resize(m);
	d.resize(n+5);
	opt.resize(n+5);
	if(m==2){
		for(int i=0;i<n;i++){
			if(p[i]!=i){
				for(int j=i+1;j<n;j++){
					if(p[j]==i){
						t[0]=i;
						t[1]=j;
						int j=Bob(t);
						swap(p[t[u[j]]], p[t[v[j]]]);
						break;
					}
				}
			}
		}
		return n;
	}
	for(int i=0;i<n;i++){
		if(p[i]==i){
			ans++;
		}
	}
	if(e>m){
		return ans;
	}
	int start=ans;
	int deg=0;
	for(int i=0;i<e;i++){
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	for(int i=0;i<m;i++){
		deg=max(deg,(int)g[i].size());
	}
	if(deg>=3){
		return ans;
	}
	find(0);
	opt[1]=1;
	for(int i=m;i<=n;i++){
		for(int j=1;j<i;j++){
			for(int l=1;l+j<i;l++){
				int r=i-j-l;
				int mn=min({opt[j]+opt[n-j],opt[l]+opt[n-l],opt[r]+opt[n-r]});
				if(mn>opt[i]){
					opt[i]=mn;
					d[i]={j,l,r};
				}
			}
		}
	}
	if(e==3){
		solve3();
		go();
		ans=0;
		for(int i=0;i<f.size();i++){
			if(f[i].size()==1){
				ans++;
			}
		}
		return ans;
	}
//		vector<int>bef(n+5,0);
//		vector<bool>dp(n+5,0);
//		dp[0]=true;
//		for(int x:v){
//			for(int i=n;i>=0;i--){
//				if(dp[i]){
//					if(i+x<=n&&!dp[i+x]){
//						dp[i+x]=true;
//						bef[i+x]=x;
//					}
//				}
//			}
//		}
//		if(!dp[n]){
//			return ans;
//		}
//		vector<int>num;
//		int cur=n;
//		while(cur>0){
//			num.pb(bef[cur]);
//			cur-=bef[cur];
//		}
//		if(e==3){
//			return ans;
//		}
	int play=n*10;
	int mx=0;
	bool reach=false;
	while(play--){
		fill(all(vis),false);
		for(int i=0;i<n;i++){
			g[i].clear();
		}
		f.clear();
		for(int i=0;i<n;i++){
			g[p[i]].pb(i);
			g[i].pb(p[i]);
		}
		for(int i=0;i<n;i++){
			if(!vis[i]){
				f.pb({});
				dfs(i);
			}
		}
		sort(all(f),[&](vector<int>a,vector<int>b){
			return (int)a.size()>(int)b.size();
		});
		vector<int>ord;
		for(int i=0;i<f.size();i++){
			for(int x:f[i]){
				ord.pb(x);
			}
		}
		for(int i=0;i<m;i++){
			t[line[i]]=ord[i];
		}
		int j=Bob(t);
		swap(p[t[u[j]]], p[t[v[j]]]);
		{
			int cnt=0;
			for(int i=0;i<n;i++){
				if(p[i]==i){
					cnt++;
				}
			}
			mx=max(mx,cnt);
			if(cnt>=max(n-m+1,start)){
				reach=true;
				break;
			}
		}
	}
	if(!reach){
		return max(n-m+1,start);
	}
	return max(n-m+1,start);
}

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