Submission #1249872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249872		PlayVoltz	Permutation Game (APIO25_permgame)	C++20	Compilation error	0 ms	0 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);
}

void even(vector<int> temp){
	int c=0;
	vector<int> res(1, temp[0]);
	for (int i=0; i<m/2-1; ++i){
		if (c%(2*(temp.size()-m)-2))++c;
		else c+=temp.size()-m;
		res.pb(temp[c]);
	}
	++c;
	res.pb(temp[c]);
	c-=s-m;
	res.pb(temp[c]);
	for (int i=0; i<m/2-2; ++i){
		if (c%(2*(temp.size()-m)-2)==1)c-=temp.size()-m;
		else --c;
		res.pb(temp[c]);
	}
	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||(!(m%2)&&ans==n-m)){
		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;
	}
	
	
	while (decomp()>m+1){
		bool got=0;
		for (auto c:vect)if (c.size()==m){
			got=1;
			bob(c);
			break;
		}
		if (!got)for (auto c:vect)if (c.size()>=m+2){
			got=1;
			even(c);
			break;
		}
		if (!got){
			int sum=0;
			for (auto c:vect)if (c.size()>=3)sum+=c.size();
			if (sum<m+2)break;
			vector<int> temp;
			for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
			temp.resize(m);
			bob(temp);
		}
	}
	while (decomp()>m+1){
		bool got=0;
		for (auto c:vect)if (c.size()==m){
			got=1;
			bob(c);
			break;
		}
		if (!got)for (auto c:vect)if (c.size()>=2*m-1){
			got=1;
			even(c);
			break;
		}
		if (!got){
			if (vect.size()==1)break;
			vector<int> temp;
			for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
			temp.resize(m);
			bob(temp);
		}
	}
	while (decomp()>m+1){
		if (vect[0].size()==m)bob(vect[0]);
		else if (vect[0].size()>=m+2)even(vect[0]);
		else{
			vector<int> temp;
			for (auto c:vect)for (auto a:c)temp.pb(a);
			temp.resize(m);
			bob(temp);
		}
	}
	return n-m-1;
}

Compilation message (stderr)

permgame.cpp: In function 'void even(std::vector<int>)':
permgame.cpp:59:12: error: 's' was not declared in this scope
   59 |         c-=s-m;
      |            ^
permgame.cpp: In function 'int Alice(int, int, std::vector<int>, std::vector<int>, int, std::vector<int>)':
permgame.cpp:157:61: error: no matching function for call to 'min(std::vector<int>::size_type, int)'
  157 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from permgame.h:1,
                 from permgame.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
permgame.cpp:157:61: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
  157 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from permgame.h:1,
                 from permgame.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
permgame.cpp:157:61: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
  157 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from permgame.h:1,
                 from permgame.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
permgame.cpp:157:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  157 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from permgame.h:1,
                 from permgame.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
permgame.cpp:157:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  157 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~
permgame.cpp:177:61: error: no matching function for call to 'min(std::vector<int>::size_type, int)'
  177 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from permgame.h:1,
                 from permgame.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
permgame.cpp:177:61: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
  177 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from permgame.h:1,
                 from permgame.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
permgame.cpp:177:61: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
  177 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from permgame.h:1,
                 from permgame.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
permgame.cpp:177:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  177 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from permgame.h:1,
                 from permgame.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
permgame.cpp:177:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  177 |                         for (auto c:vect)for (int i=0; i<min(c.size(), m-1); ++i)temp.pb(c[i]);
      |                                                          ~~~^~~~~~~~~~~~~~~