Submission #674544

#	Time	Username	Problem	Language	Result	Execution time	Memory
674544		QwertyPi	Cheerleaders (info1cup20_cheerleaders)	C++14	33 / 100	162 ms	20844 KiB

cheerleaders

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> f1(vector<int> v){
	vector<int> nv;
	int k = v.size() >> 1;
	for(int i = k; i < k * 2; i++){
		nv.push_back(v[i]);
	}
	for(int i = 0; i < k; i++){
		nv.push_back(v[i]);
	}
	return nv;
}

vector<int> f2(vector<int> v){
	vector<int> nv;
	int k = v.size() >> 1;
	for(int i = 0; i < k; i++){
		nv.push_back(v[i * 2]);
	}
	for(int i = 0; i < k; i++){
		nv.push_back(v[i * 2 + 1]);
	}
	return nv;
}

void pr(vector<int> v){
	for(auto i : v) cout << i << ' '; cout << endl;
}

void g(vector<int>& a, string s){
	vector<int> v(a.begin(), a.end());
	for(auto i : s){
		if(i == '1'){
			v = f1(v);
		}else if(i == '2'){
			v = f2(v);
		}
	}
	cout << s << ": "; pr(v);
}

int dp[1 << 17];
int b[1 << 17];

int inv(vector<int>& a, int l, int m, int r){
	int x = l, y = m;
	int id = l;
	int cnt = 0;
	while(x != m || y != r){
		if(y == r || x != m && a[x] < a[y]) b[id++] = a[x++];
		else b[id++] = a[y++], cnt += x - l;
	}
	for(int i = l; i < r; i++) a[i] = b[i];
	return cnt;
}

int test(int n, vector<int> a){
	int ans = 0;
	for(int j = 0; j < n; j++){
		int c = 0;
		for(int l = 0; l < (1 << n); l += (1 << j + 1)){
			c += inv(a, l, l + (1 << j), l + (1 << j + 1));
		}
		ans += min(c, (1 << n + j - 1) - c);
	}
	return ans;
}

int mcost[17];
int32_t main(){
	vector<int> a[17];
	int n; cin >> n;
	if(n == 0) { cout << "0\n11\n"; return 0; }
	for(int i = 0; i < (1 << n); i++){
		int v; cin >> v; a[0].push_back(v);
	}
	for(int i = 1; i < n; i++){
		a[i] = f2(a[i - 1]);
	}
	for(int i = 0; i < n; i++){
		mcost[i] = test(n, a[i]);
	}

	cout << *min_element(mcost, mcost + n) << "\n11\n"; return 0;
	vector<int> cur(1 << n);
	for(int i = 0; i < (1 << n); i++){
		cur[i] = a[0][i];
	}
	
	string ans = "11";
	while(abs(cur[1] - cur[0]) != 1)
		ans.push_back('2'), cur = f2(cur);
	for(int i = 0; i < n; i++){
		if(cur[0] > cur[1 << i]){
			for(int j = 0; j < i + 1; j++) ans.push_back('2'), cur = f2(cur);
			ans.push_back('1'), cur = f1(cur);
			for(int j = i + 1; j < n; j++) ans.push_back('2'), cur = f2(cur);
		}
	}
	cout << 0 << endl;
	cout << ans << endl;
}

/*

: 1 2 3 4 
1: 3 4 1 2 
212: 2 1 4 3 
1212: 4 3 2 1 

*/

Compilation message (stderr)

cheerleaders.cpp: In function 'void pr(std::vector<long long int>)':
cheerleaders.cpp:30:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   30 |  for(auto i : v) cout << i << ' '; cout << endl;
      |  ^~~
cheerleaders.cpp:30:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   30 |  for(auto i : v) cout << i << ' '; cout << endl;
      |                                    ^~~~
cheerleaders.cpp: In function 'long long int inv(std::vector<long long int>&, long long int, long long int, long long int)':
cheerleaders.cpp:53:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   53 |   if(y == r || x != m && a[x] < a[y]) b[id++] = a[x++];
cheerleaders.cpp: In function 'long long int test(long long int, std::vector<long long int>)':
cheerleaders.cpp:64:45: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   64 |   for(int l = 0; l < (1 << n); l += (1 << j + 1)){
      |                                           ~~^~~
cheerleaders.cpp:65:45: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   65 |    c += inv(a, l, l + (1 << j), l + (1 << j + 1));
      |                                           ~~^~~
cheerleaders.cpp:67:29: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   67 |   ans += min(c, (1 << n + j - 1) - c);
      |                       ~~~~~~^~~

• Subtask 1: 8 / 16
• Subtask 2: 5 / 10
• Subtask 3: 20 / 25
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28