oj.uz

Submission #846077

# Submission time Handle Problem Language Result Execution time Memory
846077 2023-09-07T09:17:08 Z Piokemon Cheerleaders (info1cup20_cheerleaders) C++17
100 / 100
 573 ms 16376 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int K = 17;
constexpr int N = (1<<K);
int a[N+9];
int b[N+9];
vector<vector<int>> seg[K+5];

ll zwy,rev;

void dziel(vector<int> &poz, int k){
	vector<int> one,zero; one.clear();zero.clear();
	for (int x:poz){
		if (a[x]&(1<<k)){
			one.push_back(x);
			rev += zero.size();
		}
		else{
			zero.push_back(x);
			zwy += one.size();
		}
	}
	if (k>0){
		if (one.size()>1)seg[k-1].push_back(one);
		if (zero.size()>1)seg[k-1].push_back(zero);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,k;
	cin >> k;
	n = (1<<k);
	if (k==0){
		cout << "0\n";
		cout << "222\n";
		return 0;
	}
	vector<int> temp;
	for (int x=0;x<n;x++){
		cin >> b[x];
		a[b[x]] =x;
		temp.push_back(x);
	}
	
	pair<int,int> best;
	ll inw=n*n;
	for (int rot=0;rot<=k-1;rot++){
		for (int x=0;x<=k-1;x++) seg[x].clear();
		seg[k-1].push_back(temp);
		ll ksor=0,odp=0;
		for (int z=k-1;z>=0;z--){
			zwy=0;
			rev=0;
			for (vector<int> &y:seg[z]){
				dziel(y,z);
			}
			if (zwy<rev) odp+=zwy;
			else{
				odp+=rev;
				ksor+=(1<<z);
			}
		}
		if (odp<inw){
			inw = odp;
			best = {rot,ksor};
		}
		for (int x=0;x<n;x++){
			ll temp = a[x]%2;
			a[x] = a[x]/2;
			a[x] += (temp<<(k-1));
		}
	}
	//cout << best.first << ' ' << best.second << '\n';
	cout << inw << '\n';
	for (int x=0;x<best.first;x++) cout << '2';
	for (int x=0;x<k;x++){
		cout << '2';
		if (best.second & (1<<x)) cout << '1';
	}
	cout << '\n';
}

Subtask #1
16.0 / 16.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 4188 KB Correct!
2 Correct 74 ms 4368 KB Correct!
3 Correct 164 ms 8460 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 16376 KB Correct!
2 Correct 389 ms 16204 KB Correct!
3 Correct 573 ms 16200 KB Correct!
4 Correct 569 ms 16320 KB Correct!
5 Correct 566 ms 16196 KB Correct!