Submission #674547

#	Time	Username	Problem	Language	Result	Execution time	Memory
674547		QwertyPi	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	345 ms	24536 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++], cnt += y - m;
		else b[id++] = a[y++];
	}
	for(int i = l; i < r; i++) a[i] = b[i];
	return cnt;
}

int test(int n, vector<int> a, vector<int>& data){
	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));
		}
		if(c <= (1LL << n + j - 1) - c) data.push_back(0); else data.push_back(1);
		ans += min(c, (1LL << n + j - 1) - c);
	}
	return ans;
}

int mcost[17];
int32_t main(){
	vector<int> a[17], d[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], d[i]);
	}

	int midx = 0;
	for(int i = 1; i < n; i++){
		if(mcost[i] < mcost[midx]){
			midx = i;
		}
	}
	cout << mcost[midx] << endl;
	vector<int> cur(1 << n);
	for(int i = 0; i < (1 << n); i++){
		cur[i] = a[midx][i];
	}
	string ans = "11";
	for(int i = 0; i < midx; i++)
		ans.push_back('2'), cur = f2(cur);
	for(int i = 0; i < n; i++){
		if(d[midx][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 << ans << endl;
}

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++], cnt += y - m;
cheerleaders.cpp: In function 'long long int test(long long int, std::vector<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:25: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   67 |   if(c <= (1LL << n + j - 1) - c) data.push_back(0); else data.push_back(1);
      |                   ~~~~~~^~~
cheerleaders.cpp:68:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   68 |   ans += min(c, (1LL << n + j - 1) - c);
      |                         ~~~~~~^~~

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