oj.uz

답안 #346825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
346825 2021-01-11T07:07:50 Z arnold518 Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 1347 ms 5000 KB 
#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

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.0 / 16.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 1508 KB Correct!
2 Correct 146 ms 1764 KB Correct!
3 Correct 335 ms 2900 KB Correct!

Subtask #5
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 750 ms 4720 KB Correct!
2 Correct 833 ms 4744 KB Correct!
3 Correct 1303 ms 4704 KB Correct!
4 Correct 1347 ms 5000 KB Correct!
5 Correct 1326 ms 4684 KB Correct!