oj.uz

Submission #846052

# Submission time Handle Problem Language Result Execution time Memory
846052 2023-09-07T08:46:55 Z Piokemon Cheerleaders (info1cup20_cheerleaders) C++17
33 / 100
 389 ms 16884 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;
	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;rot++){
		for (int x=0;x<=k;x++) seg[x].clear();
		seg[k].push_back(temp);
		int ksor=0,odp=0;
		for (int z=k;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++){
			bool temp = (a[x]&(1<<(k-1)))>0;
			if (temp) a[x]-=(1<<(k-1));
			a[x] = a[x]<<1;
			a[x] += temp;
		}
	}
	//cout << best.first << ' ' << best.second << '\n';
	cout << inw << '\n';
	for (int x=0;x<best.first;x++) cout << '2';
	for (int x=k;x>=0;x--){
		if (best.second & (1<<x)) cout << '1';
		cout << '2';
	}
	cout << '\n';
}

Subtask #1
8.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct!
2 Correct 0 ms 344 KB Correct number of inversions, wrong sequence of operations
3 Correct 0 ms 348 KB Correct number of inversions, wrong sequence of operations
4 Correct 0 ms 344 KB Correct number of inversions, wrong sequence of operations

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct number of inversions, wrong sequence of operations
2 Correct 1 ms 344 KB Correct number of inversions, wrong sequence of operations
3 Correct 0 ms 348 KB Correct number of inversions, wrong sequence of operations
4 Correct 1 ms 344 KB Correct number of inversions, wrong sequence of operations

Subtask #3
20.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Correct number of inversions, wrong sequence of operations
2 Correct 8 ms 600 KB Correct number of inversions, wrong sequence of operations
3 Correct 5 ms 600 KB Correct number of inversions, wrong sequence of operations
4 Correct 5 ms 600 KB Correct number of inversions, wrong sequence of operations

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 4292 KB Correct number of inversions, wrong sequence of operations
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 389 ms 16884 KB Wrong number of inversions
2 Halted 0 ms 0 KB -