Submission #428332

#	Time	Username	Problem	Language	Result	Execution time	Memory
428332		errorgorn	Cheerleaders (info1cup20_cheerleaders)	C++17	25 / 100	2081 ms	2336 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];

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>nn;
	n=1<<nn;
	
	if (n==1){
		cout<<0<<endl;
		cout<<"1"<<endl;
	}
	
	rep(x,0,n) cin>>arr[x];
	
	ll ans=1e18;
	rep(zzz,0,nn){
		//rep(x,0,n) cout<<arr[x]<<" "; cout<<endl;
		
		ll curr=0;
		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,r;
				rep(y,x,x+w) l.pub(arr[y]);
				rep(y,x+w,x+2*w) r.pub(arr[y]);
				
				sort(all(l)),sort(all(r));
				
				int idx=0;
				for (auto &it:r){
					while (idx!=sz(l) && l[idx]<it) idx++;
					
					flip+=idx,normal+=sz(l)-idx;
				}
			}
			
			curr+=min(normal,flip);
		}
		
		//cout<<curr<<endl;
		ans=min(ans,curr);
		
		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<<"1"<<endl;
}

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