Submission #525472

#	Time	Username	Problem	Language	Result	Execution time	Memory
525472		scwadr	Cheerleaders (info1cup20_cheerleaders)	C++17	72 / 100	134 ms	1960 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], 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, 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]);
	assert(rr[0] < N * 1ll * N);
	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: 0 / 28