oj.uz

Submission #520629

# Submission time Handle Problem Language Result Execution time Memory
520629 2022-01-30T11:37:20 Z amunduzbaev Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 218 ms 2632 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = (1 << 17);
int a[N + 5], n;

vector<int> make(int shift, int x){
	vector<int> res;
	while(shift--) res.push_back(2);
	for(int i=0;i<n;i++){
		res.push_back(2);
		if(x >> i & 1) res.push_back(1);
	}
	return res;
}

int tree[N << 1];
long long cc[2][20];

void add(int v, int b, int x = 1){
	tree[x]++;
	if(b == -1) return;
	if(v >> b & 1){
		cc[1][b] += tree[x << 1];
	} else {
		cc[0][b] += tree[x << 1 | 1];
	}
	
	add(v, b - 1, x << 1 | (v >> b & 1));
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n;
	for(int i=0, x;i<(1 << n);i++) cin>>x, a[x] = i;
	if(n == 0){
		cout<<0<<"\n";
		return 0;
	}
	
	ar<long long, 3> rr {N * 1ll * N};
	for(int j=0;j<n;j++){
		memset(cc, 0, sizeof cc);
		memset(tree, 0, sizeof tree);
		for(int i=0;i<(1 << n);i++){
			add(a[i], n - 1);
			a[i] = ((a[i] & 1) << (n - 1)) | (a[i] >> 1);
		}
		int x = 0; long long res = 0;
		for(int i=0;i<n;i++){
			if(cc[0][i] <= cc[1][i]) res += cc[0][i];
			else res += cc[1][i], x |= (1 << i);
		}
		rr = min(rr, {res, j, x});
	}
	
	vector<int> res = make(rr[1], rr[2]);
	cout<<rr[0]<<"\n";
	for(auto x : res) cout<<x;
	cout<<"\n";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct!
2 Correct 1 ms 1228 KB Correct!
3 Correct 1 ms 1228 KB Correct!
4 Correct 1 ms 1228 KB Correct!

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1356 KB Correct!
2 Correct 30 ms 1356 KB Correct!
3 Correct 67 ms 1580 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 1828 KB Correct!
2 Correct 125 ms 2608 KB Correct!
3 Correct 218 ms 2632 KB Correct!
4 Correct 215 ms 2624 KB Correct!
5 Correct 215 ms 2624 KB Correct!