Submission #428355

#	Time	Username	Problem	Language	Result	Execution time	Memory
428355		errorgorn	Cheerleaders (info1cup20_cheerleaders)	C++17	100 / 100	1010 ms	18768 KiB

cheerleaders

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

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,nn;
int arr[132000];
vector<int> v[132000];

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>nn;
	n=1<<nn;
	
	if (n==1){
		cout<<0<<endl;
		return 0;
	}
	
	rep(x,0,n) cin>>arr[x];
	
	ll ans=1e18;
	string st="";
	
	rep(zzz,0,nn){
		//rep(x,0,n) cout<<arr[x]<<" "; cout<<endl;
		rep(x,0,n) v[x].clear(),v[x].pub(arr[x]);
		
		ll curr=0;
		string s=string(zzz,'2');
		
		for (int w=1;w<n;w<<=1){
			ll normal=0,flip=0;
			
			for (int x=0;x<n;x+=2*w){
				vector<int> l=v[x],r=v[x+w];
				
				int idx=0;
				for (auto &it:r){
					while (idx!=sz(l) && l[idx]<it) idx++;
					
					flip+=idx,normal+=sz(l)-idx;
				}
				
				vector<int> temp;
				while (!l.empty() && !r.empty()){
					if (l.back()>r.back()) temp.pub(l.back()),l.pob();
					else temp.pub(r.back()),r.pob();
				}
				while (!l.empty()) temp.pub(l.back()),l.pob();
				while (!r.empty()) temp.pub(r.back()),r.pob();
				
				reverse(all(temp));
				v[x]=temp;
			}
			
			//cout<<normal<<" "<<flip<<endl;
			
			s+='2';
			if (flip<normal){
				curr+=flip;
				s+='1';
			}
			else{
				curr+=normal;
			}
		}
		
		//cout<<curr<<endl;
		if (curr<ans){
			ans=curr;
			st=s;
		}
		
		int temp[132000];
		rep(x,0,n){
			int xx=(x|((x&1)<<nn))>>1;
			temp[xx]=arr[x];
		}
		swap(arr,temp);
	}
	
	cout<<ans<<endl;
	cout<<st<<endl;
}

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