제출 #520625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520625		amunduzbaev	Cheerleaders (info1cup20_cheerleaders)	C++14	56 / 100	151 ms	2644 KiB

cheerleaders

#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = (1 << 17);
int a[N + 5], n;

vector<int> make(int shift, int x){
	vector<int> res;
	while(shift--) res.push_back(2);
	for(int i=0;i<n;i++){
		res.push_back(2);
		if(x >> i & 1) res.push_back(1);
	}
	return res;
}

int tree[N << 1], cc[2][20];

void add(int v, int b, int x = 1){
	tree[x]++;
	if(b == -1) return;
	if(v >> b & 1){
		cc[1][b] += tree[x << 1];
	} else {
		cc[0][b] += tree[x << 1 | 1];
	}
	
	add(v, b - 1, x << 1 | (v >> b & 1));
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n;
	for(int i=0, x;i<(1 << n);i++) cin>>x, a[x] = i;
	ar<long long, 3> rr {N * 1ll * N};
	for(int j=0;j<n;j++){
		memset(cc, 0, sizeof cc);
		memset(tree, 0, sizeof tree);
		for(int i=0;i<(1 << n);i++){
			add(a[i], n - 1);
			a[i] = ((a[i] & 1) << (n - 1)) | (a[i] >> 1);
		}
		
		for(int i=0;i<(1 << n);i++){
			int res = 0;
			for(int j=0;j<n;j++){
				res += cc[(i >> j & 1)][j];
			}
			
			rr = min(rr, {res, j, i});
		}
	}
	//~ cout<<rr[1]<<" "<<rr[2]<<"\n";
	vector<int> res = make(rr[1], rr[2]);
	cout<<rr[0]<<"\n";
	for(auto x : res) cout<<x;
	cout<<"\n";
}

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