Submission #1028997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028997		vjudge1	Cheerleaders (info1cup20_cheerleaders)	C++17	54 / 100	309 ms	12576 KiB

cheerleaders

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

#define int long long

void f(){
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	//f();
	int n; cin >> n;
	vector<int> a((1<<n)), pos((1<<n));
	for(auto &i: a) cin >> i;

	for(int i=0; i<(1<<n); i++){
		pos[a[i]]=i;
	}

	auto get_xor=[&](int y){
		vector<int> op;
		for(int i=0; i<n; i++){
			op.push_back(1);
 			if((1<<i)&y){
				op.push_back(0);
			}
		}

		return op;
	};

	//1 is odd even thing
	//0 is swapping first half and last half
	auto d=[&](vector<int> &g, int type){
		if(type==1){
			for(int i=0; i<g.size(); i++){
				if(g[i]%2){
					g[i]=g[i]/2+(1<<(n-1));
				}
				else g[i]/=2;
			}
		}
		else{
			for(int i=0; i<n; i++){
				g[i]^=(1<<(n-1));
			}
		}
	};


	int ans=1e18;
	vector<int> op;
	for(int i=0; i<=n; i++){
		vector cnt(n, vector((1<<n), 0));
		vector<array<int, 2>> p(n);
		
		for(int l=0; l<(1<<n); l++){
			int val=0;
			for(int j=n-1; j>=0; j--){
				if(pos[l]&(1<<j)){
					p[j][1]+=cnt[j][val];

					val+=(1<<j);
				}
				else{
					p[j][0]+=cnt[j][val+(1<<j)];

				}
				cnt[j][val]++;
			}
		}
	
		int sum=0, xo=0;
		for(int i=0; i<n; i++){
			if(p[i][1]<p[i][0]) xo+=(1<<i);
		 	sum+=min(p[i][0], p[i][1]);
		}


		if(sum<ans){
			ans=sum;
			vector<int> val=get_xor(xo);
			op.clear();
			for(int l=0; l<i; l++) op.push_back(0);
			for(auto l: val) op.push_back(l);
		}


		d(pos, 1);
		
	}

	if(n==0) ans=0;

	cout<<ans<<"\n";
	for(auto i: op) cout<<(i==0?1:2);
}	

Compilation message (stderr)

cheerleaders.cpp: In lambda function:
cheerleaders.cpp:42:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int i=0; i<g.size(); i++){
      |                 ~^~~~~~~~~
cheerleaders.cpp: In function 'void f()':
cheerleaders.cpp:8:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  freopen("in.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cheerleaders.cpp:9:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  freopen("out.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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