제출 #845935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
845935		Piokemon	Cheerleaders (info1cup20_cheerleaders)	C++17	0 / 100	79 ms	4780 KiB

cheerleaders

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

constexpr int K = 16;
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;
	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);
	vector<int> temp;
	for (int x=1;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;rot++){
		for (int x=0;x<=k;x++) seg[x].clear();
		seg[k].push_back(temp);
		int ksor=0,odp=0;
		for (int z=k;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=1;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 << inw << '\n';
	for (int x=0;x<best.first;x++) cout << '2';
	for (int x=k-1;x>=0;x--){
		if (best.second & (1<<x)) cout << '1';
		cout << '2';
	}
	cout << '\n';
}

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