oj.uz

답안 #362628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362628 2021-02-03T18:15:24 Z ogibogi2004 Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 763 ms 22036 KB 
#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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Correct!
2 Correct 1 ms 492 KB Correct!
3 Correct 1 ms 492 KB Correct!
4 Correct 1 ms 492 KB Correct!

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Correct!
2 Correct 1 ms 492 KB Correct!
3 Correct 1 ms 492 KB Correct!
4 Correct 1 ms 640 KB Correct!

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 748 KB Correct!
2 Correct 6 ms 748 KB Correct!
3 Correct 6 ms 748 KB Correct!
4 Correct 6 ms 748 KB Correct!

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 5996 KB Correct!
2 Correct 95 ms 5868 KB Correct!
3 Correct 219 ms 11628 KB Correct!

Subtask #5
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 508 ms 22036 KB Correct!
2 Correct 544 ms 22016 KB Correct!
3 Correct 744 ms 22036 KB Correct!
4 Correct 735 ms 21996 KB Correct!
5 Correct 763 ms 21940 KB Correct!