Submission #674541

#	Time	Username	Problem	Language	Result	Execution time	Memory
674541		QwertyPi	Cheerleaders (info1cup20_cheerleaders)	C++14	21 / 100	2063 ms	7256 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;
}

vector<int> a;
void g(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(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 || a[x] < b[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;
}


int32_t main(){
	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.push_back(v);
	}

	vector<int> cur(1 << n);
	for(int i = 0; i < (1 << n); i++){
		cur[i] = a[i];
	}

	string ans = "11";
	while(abs(cur[1] - cur[0]) != 1)
		ans.push_back('2'), cur = f2(cur);
	// for(auto i : cur) cout << i << ' '; cout << endl;
	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;
	// for(auto i : cur) cout << i << ' '; cout << 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;
      |                                    ^~~~

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