Submission #362628

#	Time	Username	Problem	Language	Result	Execution time	Memory
362628		ogibogi2004	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	763 ms	22036 KiB

cheerleaders

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=(1<<17);
ll where[MAXN];
ll ans=MAXN*MAXN,n;
vector<ll>out;
ll pref[20][MAXN];
ll cnt0[20],cnt1[20];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	vector<ll>v;
	for(ll i=1;i<=(1<<n);++i)
	{
		ll x;
		cin>>x;
		where[x]=i-1;
	}
	for(ll i=1;i<=n+20;i++)
	{
		//cout<<i<<endl;
		for(ll j=0;j<20;j++)cnt1[j]=0;
		for(ll j=0;j<20;j++)cnt0[j]=0;
		for(ll j=0;j<20;j++)
		{
			for(ll k=0;k<(1<<n);k++)pref[j][k]=0;
		}
		//for(ll j=0;j<(1<<n);j++)cout<<where[j]<<" ";
		//cout<<endl;
		for(ll j=0;j<(1<<n);j++)
		{
			ll l=where[j];
			//cout<<">>>"<<j<<":\n";
			for(ll g=1;g<=n;g++)
			{
				//cout<<l<<" "<<pref[g-1][l^1]<<endl;
				if(l&1)cnt1[g-1]+=pref[g-1][l^1];
				else cnt0[g-1]+=pref[g-1][l^1];
				l/=2;
			}
			l=where[j];
			for(ll g=0;g<n;g++)
			{
				pref[g][l]++;
				l/=2;
			}
		}
		//cout<<endl<<endl;
		ll mask=0,cntinv=0;
		/*for(ll j=0;j<4;j++)
		{
			for(ll l=0;l<(1<<n);l++)
			{
				cout<<j<<" "<<l<<" "<<pref[j][l]<<endl;
			}
		}*/
		for(ll j=0;j<20;j++)
		{
			//cout<<cnt0[j]<<" "<<cnt1[j]<<endl;
			if(j>=n-i&&cnt1[j]<cnt0[j])
			{
				cntinv+=cnt1[j];
				mask|=(1<<j);
			}
			else
			{
				cntinv+=cnt0[j];
			}
		}
		if(cntinv<ans)
		{
			//cout<<"uwu "<<mask<<endl;
			ans=cntinv;
			out.clear();
			for(ll j=i-1;j>0;j--)
			{
				if(n-i+j>=0&&mask&(1<<(n-i+j)))
				{
					out.push_back(1);
				}
				out.push_back(2);
			}
			if(n-i>=0&&mask&(1<<(n-i)))out.push_back(1);
			reverse(out.begin(),out.end());
		}
		for(ll j=0;j<(1<<n);j++)
		{
			where[j]=(where[j]>>1)|((where[j]&1)<<(n-1));
		}
	}
	cout<<ans<<endl;
	for(auto xd:out)cout<<xd;
return 0;
}

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