oj.uz

Submission #845935

# Submission time Handle Problem Language Result Execution time Memory
845935 2023-09-06T20:18:15 Z Piokemon Cheerleaders (info1cup20_cheerleaders) C++17
0 / 100
 79 ms 4780 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int K = 16;
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);
	vector<int> temp;
	for (int x=1;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=1;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 << inw << '\n';
	for (int x=0;x<best.first;x++) cout << '2';
	for (int x=k-1;x>=0;x--){
		if (best.second & (1<<x)) cout << '1';
		cout << '2';
	}
	cout << '\n';
}

Subtask #1
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct!
2 Incorrect 0 ms 348 KB Wrong number of inversions
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 25.0

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

Subtask #4
0.0 / 21.0

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

Subtask #5
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -