Submission #1028907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028907		vjudge1	Cheerleaders (info1cup20_cheerleaders)	C++17	0 / 100	256 ms	12548 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));
	for(auto &i: a) cin >> i;

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

		return op;
	};

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

	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(a[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]);
		}

		vector<int> val=get_xor(xo);

		if(sum<ans){
			ans=sum;

			op.clear();
			for(int l=0; l<i; l++) op.push_back(0);
			for(auto l: val) op.push_back(l);
		}


		d(a, 0);
		
	}

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

Compilation message (stderr)

cheerleaders.cpp: In lambda function:
cheerleaders.cpp:26:9: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
   26 |    if((1<<i)&&y){
      |       ~~^~~~
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: 0 / 16
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28