Submission #1027699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027699		vjudge1	Cheerleaders (info1cup20_cheerleaders)	C++17	16 / 100	2043 ms	126848 KiB

cheerleaders

#include <bits/stdc++.h>

using namespace std;

typedef long long lo; 

#define fi first
#define se second
#define endl "\n"
#define pb push_back
#define int long long
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
#define _ << " " <<

const lo inf = 1000000000;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,a[li],k,flag,t,b[li],tree[li*4];
int cev;
string s;
vector<int> v;

inline void build(int node,int start,int end){
	tree[node]=0;
	if(start==end)return ;
	build(node*2,start,mid),build(node*2+1,mid+1,end);
}

inline void update(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){tree[node]++;return ;}
	update(node*2,start,mid,l,r),update(node*2+1,mid+1,end,l,r);
	tree[node]=tree[node*2]+tree[node*2+1];
}

inline int query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	if(start>=l && end<=r)return tree[node];
	return query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r);
}

int32_t main(void){
	fio();
	cin>>n;
	m=(1<<n);
	for(int i=1;i<=m;i++){
		cin>>a[i];
		b[i]=a[i];
		v.pb(a[i]);
	}
	sort(b+1,b+m+1);
	for(int i=0;i<m;i++){
		v[i]=lower_bound(b+1,b+m+1,v[i])-b;
	}
	queue<pair<vector<int>,string>> q;
	q.push({v,s});
	map<vector<int>,bool> vis;
	int mn=inf;
	string ans="";
	int total=0;
	srand(time(NULL));
	while(q.size()){
		v=q.front().fi;
		s=q.front().se;
		q.pop();
		if(vis[v])continue;
		vis[v]=1;
		build(1,1,m);
		cev=0;
		for(int i=0;i<m;i++){
			cev+=query(1,1,m,v[i]+1,m);update(1,1,m,v[i],v[i]);
		}
		//~ cout<<cev _ s<<en	dl;
		if(cev<mn){mn=cev;ans=s;}
		vector<int> v1,v2;
		for(int i=m/2;i<m;i++)v1.pb(v[i]);
		for(int i=0;i<m/2;i++)v1.pb(v[i]);
		for(int i=0;i<m;i+=2)v2.pb(v[i]);
		for(int i=1;i<m;i+=2)v2.pb(v[i]);
		int at=rand()%10;
		if(at<=8 && vis.find(v1)==vis.end())q.push({v1,s+'1'});
		if(at>3 && vis.find(v2)==vis.end())q.push({v2,s+'2'});
		total++;
		//~ if(total>500)break;
	}
	cout<<mn<<endl<<ans<<endl;
	return 0;
}

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