Submission #520629

#	Time	Username	Problem	Language	Result	Execution time	Memory
520629		amunduzbaev	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	218 ms	2632 KiB

cheerleaders

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

#define ar array

const int N = (1 << 17);
int a[N + 5], n;

vector<int> make(int shift, int x){
	vector<int> res;
	while(shift--) res.push_back(2);
	for(int i=0;i<n;i++){
		res.push_back(2);
		if(x >> i & 1) res.push_back(1);
	}
	return res;
}

int tree[N << 1];
long long cc[2][20];

void add(int v, int b, int x = 1){
	tree[x]++;
	if(b == -1) return;
	if(v >> b & 1){
		cc[1][b] += tree[x << 1];
	} else {
		cc[0][b] += tree[x << 1 | 1];
	}
	
	add(v, b - 1, x << 1 | (v >> b & 1));
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n;
	for(int i=0, x;i<(1 << n);i++) cin>>x, a[x] = i;
	if(n == 0){
		cout<<0<<"\n";
		return 0;
	}
	
	ar<long long, 3> rr {N * 1ll * N};
	for(int j=0;j<n;j++){
		memset(cc, 0, sizeof cc);
		memset(tree, 0, sizeof tree);
		for(int i=0;i<(1 << n);i++){
			add(a[i], n - 1);
			a[i] = ((a[i] & 1) << (n - 1)) | (a[i] >> 1);
		}
		int x = 0; long long res = 0;
		for(int i=0;i<n;i++){
			if(cc[0][i] <= cc[1][i]) res += cc[0][i];
			else res += cc[1][i], x |= (1 << i);
		}
		rr = min(rr, {res, j, x});
	}
	
	vector<int> res = make(rr[1], rr[2]);
	cout<<rr[0]<<"\n";
	for(auto x : res) cout<<x;
	cout<<"\n";
}

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