oj.uz

Submission #428430

# Submission time Handle Problem Language Result Execution time Memory
428430 2021-06-15T11:45:28 Z oolimry Cheerleaders (info1cup20_cheerleaders) C++17
100 / 100
 670 ms 25624 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;

vector<int> original;
vector<int> arr[140005];
vector<int> nxt;
vector<int> temp;

lint ans = 1152921504606846976LL;
lint res = 0;

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	int N = (1<<n);
	original.resize(N);
	for(int i = 0;i < N;i++) cin >> original[i];
	
	if(n == 0){
		cout << 0;
		return 0;
	}
	
	int bestiter = -1; vector<int> bestflips;
	for(int iter = 0;iter < n;iter++){
		for(int i = 0;i < N;i++) arr[i].clear();
		for(int i = 0;i < N;i++) arr[i].push_back(original[i]);
		
		res = 0;
		
		vector<int> flips;
		for(lint gap = 1;gap < N;gap *= 2){
			lint invcnt = 0;
			lint total = 0;
			
			for(int s = 0;s < N;s += 2*gap){
				int m = s+gap;
				lint l = 0;
				for(int r : arr[m]){
					while(l < sz(arr[s])){
						if(arr[s][l] > r) break;
						else l++;
					}
					invcnt += (gap-l);
				}
				total += gap*gap;
				
				swap(temp, arr[s]);
				arr[s].resize(sz(temp) + sz(arr[m]));
				merge(all(temp), all(arr[m]), arr[s].begin());
				temp.clear();
			}

			//if(iter == 0) show(invcnt);
			if(total-invcnt < invcnt){
				res += total-invcnt;
				flips.push_back(1);
			}
			else{
				res += invcnt;
				flips.push_back(0);
			}
		}
		
		reverse(all(flips));
		if(ans > res){
			ans = res;
			bestiter = iter;
			bestflips = flips;
		}
		
		nxt.clear();
		for(int i = 0;i < N;i += 2) nxt.push_back(original[i]);
		for(int i = 1;i < N;i += 2) nxt.push_back(original[i]);
		swap(nxt, original);
	}
	
	string S = "";
//	show(bestiter);
	for(int i = 0;i < bestiter;i++) S += "2";
	for(int i = 0;i < n;i++){
		//show(bestflips[i]);
		if(bestflips[i]) S += "1";
		for(int j = 0;j < n-1;j++) S += "2";
	}
	
	for(char c : S){
		if(c == '2'){
			nxt.clear();
			for(int i = 0;i < N;i += 2) nxt.push_back(original[i]);
			for(int i = 1;i < N;i += 2) nxt.push_back(original[i]);
			swap(nxt, original);
		}
		else{
			for(int i = 0;i < N/2;i++) swap(original[i], original[i+N/2]);
		}
		//show(c);
		//for(int x : original) cerr << x << " "; cerr << endl;
	}
	
	
	
	cout << ans << '\n';
	cout << S;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3532 KB Correct!
2 Correct 2 ms 3532 KB Correct!
3 Correct 2 ms 3532 KB Correct!
4 Correct 3 ms 3532 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3532 KB Correct!
2 Correct 2 ms 3532 KB Correct!
3 Correct 3 ms 3532 KB Correct!
4 Correct 3 ms 3532 KB Correct!

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3788 KB Correct!
2 Correct 7 ms 3788 KB Correct!
3 Correct 6 ms 3788 KB Correct!
4 Correct 7 ms 3840 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8600 KB Correct!
2 Correct 51 ms 8728 KB Correct!
3 Correct 115 ms 14496 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 25540 KB Correct!
2 Correct 350 ms 25624 KB Correct!
3 Correct 666 ms 25480 KB Correct!
4 Correct 670 ms 25616 KB Correct!
5 Correct 660 ms 25520 KB Correct!