Submission #845375

#	Time	Username	Problem	Language	Result	Execution time	Memory
845375		Piokemon	Cheerleaders (info1cup20_cheerleaders)	C++17	26 / 100	227 ms	1048576 KiB

cheerleaders

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

map<vector<int>,int> numer;
int ter=1;
pair<int,int> skad[(int)4e7+9];
vector<int> stare[(int)4e7+9];

void dfs(int nr){
	vector<int> a;
	a = stare[nr];
	//cout << nr << ' ';
	//for (int x:a) cout << x << ' ';
	//cout << '\n';
	for (int x=0;x<a.size()/2;x++) swap(a[x],a[x+a.size()/2]);
	if (numer[a] == 0){
		numer[a] = ter++;
		stare[ter-1] = a;
		skad[ter-1] = {nr,1};
		dfs(ter-1);
	}
	a.clear();
	for (int x=0;x<stare[nr].size();x+=2) a.push_back(stare[nr][x]);
	for (int x=1;x<stare[nr].size();x+=2) a.push_back(stare[nr][x]);
	if (numer[a] == 0){
		numer[a] = ter++;
		stare[ter-1] = a;
		skad[ter-1] = {nr,2};
		dfs(ter-1);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,a;
	cin >> n;
	n = (1<<n);
	vector<int> pocz;
	for (int x=0;x<n;x++){
		cin >> a;
		pocz.push_back(a);
	}
	if (n==0){
		cout << "0\n";
		return 0;
	}
	numer[pocz] = ter++;
	stare[1] = pocz;
	dfs(numer[pocz]);
	int inw=1e9,best=0;
	for (int x=1;x<ter;x++){
		pocz = stare[x];
		int temp=0;
		for (int i=0;i<n;i++){
			for (int j=i+1;j<n;j++){
				if (pocz[i]>pocz[j])temp++;
			}
		}
		if (temp<inw){
			inw = temp;
			best= x;
		}
	}
	cout << inw << '\n';
	vector<char> odp;
	while(best!=1){
		//cout << best << '\n';
		odp.push_back('0'+skad[best].second);
		best = skad[best].first;
	}
	for (int x=odp.size()-1;x>=0;x--) cout << odp[x];
}

Compilation message (stderr)

cheerleaders.cpp: In function 'void dfs(int)':
cheerleaders.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int x=0;x<a.size()/2;x++) swap(a[x],a[x+a.size()/2]);
      |               ~^~~~~~~~~~~
cheerleaders.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int x=0;x<stare[nr].size();x+=2) a.push_back(stare[nr][x]);
      |               ~^~~~~~~~~~~~~~~~~
cheerleaders.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int x=1;x<stare[nr].size();x+=2) a.push_back(stare[nr][x]);
      |               ~^~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28