Submission #846063

#	Time	Username	Problem	Language	Result	Execution time	Memory
846063		Piokemon	Cheerleaders (info1cup20_cheerleaders)	C++17	54 / 100	584 ms	17396 KiB

cheerleaders

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

constexpr int K = 17;
constexpr int N = (1<<K);
int a[N+9];
int b[N+9];
vector<vector<int>> seg[K+5];

ll zwy,rev;

void dziel(vector<int> &poz, int k){
	vector<int> one,zero; one.clear();zero.clear();
	for (int x:poz){
		if (a[x]&(1<<k)){
			one.push_back(x);
			rev += zero.size();
		}
		else{
			zero.push_back(x);
			zwy += one.size();
		}
	}
	if (k>0){
		if (one.size()>1)seg[k-1].push_back(one);
		if (zero.size()>1)seg[k-1].push_back(zero);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,k;
	cin >> k;
	n = (1<<k);
	if (k==0){
		cout << "0\n";
		cout << "222\n";
		return 0;
	}
	vector<int> temp;
	for (int x=0;x<n;x++){
		cin >> b[x];
		a[b[x]] =x;
		temp.push_back(x);
	}
	
	pair<int,int> best;
	ll inw=n*n;
	for (int rot=0;rot<=k-1;rot++){
		for (int x=0;x<=k-1;x++) seg[x].clear();
		seg[k-1].push_back(temp);
		ll ksor=0,odp=0;
		for (int z=k-1;z>=0;z--){
			zwy=0;
			rev=0;
			for (vector<int> &y:seg[z]){
				dziel(y,z);
			}
			if (zwy<rev) odp+=zwy;
			else{
				odp+=rev;
				ksor+=(1<<z);
			}
		}
		if (odp<inw){
			inw = odp;
			best = {rot,ksor};
		}
		for (int x=0;x<n;x++){
			bool temp = (a[x]&(1<<(k-1)))>0;
			if (temp) a[x]-=(1<<(k-1));
			a[x] = a[x]<<1;
			a[x] += temp;
		}
	}
	//cout << best.first << ' ' << best.second << '\n';
	cout << inw << '\n';
	for (int x=0;x<best.first;x++) cout << '2';
	cout << '2';
	for (int x=0;x<k;x++){
		if (best.second & (1<<x)) cout << '1';
		if (x<k-1) cout << '2';
	}
	cout << '\n';
}

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