Submission #339748

#	Time	Username	Problem	Language	Result	Execution time	Memory
339748		wwdd	Cheerleaders (info1cup20_cheerleaders)	C++14	54 / 100	1122 ms	32168 KiB

cheerleaders

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
const ll INFL = 1e18;
vl w;
vl wa,wi;
void shuf(int n) {
	vl x(w.size(),0);
	for(int i=0;i<w.size();i++) {
		int nx = (i>>1) + ((i&1)<<(n-1));
		x[nx] = w[i];
	}
	w = x;
	wa.assign(n,0);
	wi.assign(n,-1);
}
void proc(int n) {
	vector<vl> wo[2] = {{w.size(),vl()},{w.size(),vl()}};
	int cu = 0;
	for(int i=0;i<w.size();i++) {
		wo[cu][i].push_back(w[i]);
	}
	for(int k=0;k<n;k++) {
		ll res[2] = {0,0};
		int nu = 1-cu;
		for(int i=0;i<w.size();i+=(1<<(k+1))) {
			for(int j=0;j<2;j++) {
				int pt = 0;
				for(int l=0;l<wo[cu][i^(j<<k)].size();l++) {
					while(pt < wo[cu][i^((1^j)<<k)].size() && wo[cu][i^((1^j)<<k)][pt] < wo[cu][i^(j<<k)][l]) {
						pt++;
					}
					res[j] += pt;
				}
			}
			wo[nu][i].resize((1<<(k+1)));
			merge(wo[cu][i].begin(),wo[cu][i].end(),
					wo[cu][i+(1<<k)].begin(),wo[cu][i+(1<<k)].end(),
					wo[nu][i].begin());
		}
		wa[k] = min(res[0],res[1]);
		wi[k] = res[0] > res[1];
		cu = nu;
	}
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin >> n;
	ll m = 1<<n;
	wa.assign(n,0);
	wi.assign(n,-1);
	for(int i=0;i<m;i++) {
		ll t;
		cin >> t;
		w.push_back(t);
	}
	if(n == 0) {
		cout << 0 << '\n';
		cout << 2 << '\n';
		return 0;
	}
	ll ma = INFL;
	pl st = {0,0};
	for(int i=0;i<n;i++) {
		ll res = 0;
		ll rb = 0;
		proc(n);
		for(int j=0;j<n;j++) {
			res += wa[j];
			rb |= wi[j]<<j;
		}
		if(res < ma) {
			ma = res;
			st = {i,rb};
		}
		shuf(n);
	}
	cout << ma << '\n';
	for(int i=0;i<st.first;i++) {
		cout << "2";
	}
	st.second = (st.second<<1)|((st.second&(1<<(n-1))>>(n-1)));
	for(int i=0;i<n;i++) {
		if((st.second)&(1<<i)) {
			cout << "1";
		}
		cout << "2";
	}
	cout << '\n';
}

Compilation message (stderr)

cheerleaders.cpp: In function 'void shuf(int)':
cheerleaders.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~
cheerleaders.cpp: In function 'void proc(int)':
cheerleaders.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~
cheerleaders.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i=0;i<w.size();i+=(1<<(k+1))) {
      |               ~^~~~~~~~~
cheerleaders.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int l=0;l<wo[cu][i^(j<<k)].size();l++) {
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~
cheerleaders.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |      while(pt < wo[cu][i^((1^j)<<k)].size() && wo[cu][i^((1^j)<<k)][pt] < wo[cu][i^(j<<k)][l]) {
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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