Submission #339735

#	Time	Username	Problem	Language	Result	Execution time	Memory
339735		wwdd	Cheerleaders (info1cup20_cheerleaders)	C++14	25 / 100	2037 ms	3688 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, int k) {
	ll res[2] = {0,0};
	for(int i=0;i<w.size();i+=(1<<(k+1))) {
		vl wo[2];
		for(int j=0;j<(1<<k);j++) {
			wo[0].push_back(w[j+i]);
			wo[1].push_back(w[j+i+(1<<k)]);
		}
		sort(wo[0].begin(),wo[0].end());
		sort(wo[1].begin(),wo[1].end());
		for(int j=0;j<2;j++) {
			int pt = 0;
			for(int l=0;l<wo[j].size();l++) {
				while(pt < wo[1^j].size() && wo[1^j][pt] < wo[j][l]) {
					pt++;
				}
				res[j] += pt;
			}
		}
	}
	wa[k] = min(res[0],res[1]);
	wi[k] = res[0] > res[1];
}
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);
	}
	ll ma = INFL;
	pl st = {0,0};
	for(int i=0;i<n;i++) {
		ll res = 0;
		ll rb = 0;
		for(int j=0;j<n;j++) {
			proc(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";
	}
	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, int)':
cheerleaders.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<w.size();i+=(1<<(k+1))) {
      |              ~^~~~~~~~~
cheerleaders.cpp:31:17: 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[j].size();l++) {
      |                ~^~~~~~~~~~~~~
cheerleaders.cpp:32:14: 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[1^j].size() && wo[1^j][pt] < wo[j][l]) {
      |           ~~~^~~~~~~~~~~~~~~~

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