Submission #346825

#	Time	Username	Problem	Language	Result	Execution time	Memory
346825		arnold518	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	1347 ms	5000 KiB

cheerleaders

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 17;
const int MAXM = (1<<MAXN);

int N, A[MAXM+10], B[MAXM+10];
ll C[MAXN+10][2];

void solve(int bit, vector<pii> &V)
{
	if(bit<0) return;
	vector<pii> L, R;
	for(int i=0; i<V.size(); i++)
	{
		if(V[i].second&(1<<bit)) L.push_back(V[i]);
		else R.push_back(V[i]);
	}

	ll p1=0, p2=0;
	for(int i=0, j=0; i<L.size(); i++)
	{
		for(; j<R.size() && R[j].first<L[i].first; j++);
		p1+=j;
	}

	for(int i=0, j=0; i<R.size(); i++)
	{
		for(; j<L.size() && L[j].first<R[i].first; j++);
		p2+=j;
	}

	C[bit][0]+=p1;
	C[bit][1]+=p2;
	solve(bit-1, L);
	solve(bit-1, R);
}

int main()
{
	scanf("%d", &N);
	for(int i=0; i<(1<<N); i++) scanf("%d", &A[i]);

	ll ans=1e18;
	string ans2="";
	for(int i=0; i<=N; i++)
	{
		for(int j=0; j<(1<<i); j++)
		{
			for(int k=0; k<(1<<(N-i)); k++)
			{
				B[(j<<(N-i))|k]=A[(k<<i)|j];
			}
		}

		for(int j=0; j<N; j++) C[j][0]=C[j][1]=0;

		vector<pii> V;
		for(int j=0; j<(1<<N); j++) V.push_back({B[j], j});
		sort(V.begin(), V.end());
		solve(N-1, V);

		ll t=0;
		for(int j=0; j<N; j++) t+=min(C[j][0], C[j][1]);

		string t2=string(i, '2');
		for(int j=0; j<N; j++)
		{
			t2+="2";
			if(C[j][0]<C[j][1]) t2+="1";
		}
		/*
		printf("%d : %lld ", i, t);
		cout<<t2<<'\n';
		for(int j=0; j<(1<<N); j++) printf("%d ", B[j]); printf("\n");
		for(int j=0; j<N; j++) printf("%lld ", C[j][0]); printf("\n");
		for(int j=0; j<N; j++) printf("%lld ", C[j][1]); printf("\n");

		printf("\n");
*/
		if(ans>t)
		{
			ans=t;
			ans2=t2;
		}
	}
	printf("%lld\n", ans);
	cout<<ans2<<'\n';
}

Compilation message (stderr)

cheerleaders.cpp: In function 'void solve(int, std::vector<std::pair<int, int> >&)':
cheerleaders.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0; i<V.size(); i++)
      |               ~^~~~~~~~~
cheerleaders.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0, j=0; i<L.size(); i++)
      |                    ~^~~~~~~~~
cheerleaders.cpp:27:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(; j<R.size() && R[j].first<L[i].first; j++);
      |         ~^~~~~~~~~
cheerleaders.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=0, j=0; i<R.size(); i++)
      |                    ~^~~~~~~~~
cheerleaders.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(; j<L.size() && L[j].first<R[i].first; j++);
      |         ~^~~~~~~~~
cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
cheerleaders.cpp:46:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  for(int i=0; i<(1<<N); i++) scanf("%d", &A[i]);
      |                              ~~~~~^~~~~~~~~~~~~

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