oj.uz

답안 #428355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428355 2021-06-15T10:48:48 Z errorgorn Cheerleaders (info1cup20_cheerleaders) C++17
100 / 100
 1010 ms 18768 KB 
#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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3916 KB Correct!
2 Correct 6 ms 4428 KB Correct!
3 Correct 6 ms 4428 KB Correct!
4 Correct 5 ms 4428 KB Correct!

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4452 KB Correct!
2 Correct 4 ms 4428 KB Correct!
3 Correct 6 ms 4448 KB Correct!
4 Correct 4 ms 4428 KB Correct!

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 4584 KB Correct!
2 Correct 12 ms 4556 KB Correct!
3 Correct 13 ms 4632 KB Correct!
4 Correct 14 ms 4556 KB Correct!

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 7688 KB Correct!
2 Correct 124 ms 7780 KB Correct!
3 Correct 266 ms 11172 KB Correct!

Subtask #5
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 632 ms 18284 KB Correct!
2 Correct 646 ms 18236 KB Correct!
3 Correct 1008 ms 18272 KB Correct!
4 Correct 966 ms 18768 KB Correct!
5 Correct 1010 ms 18752 KB Correct!