Submission #299696

#	Time	Username	Problem	Language	Result	Execution time	Memory
299696		E869120	Cheerleaders (info1cup20_cheerleaders)	C++14	72 / 100	2040 ms	5300 KiB

cheerleaders

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

long long N;
long long A[1 << 18], B[1 << 18];
long long c1[22], c2[22];

void dfs(int l, int r, int dep) {
	if (r - l == 1) return;
	
	int m = (l + r) / 2;
	vector<long long> v1; for (int i = l; i < m; i++) v1.push_back(A[i]);
	vector<long long> v2; for (int i = m; i < r; i++) v2.push_back(A[i]);
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	for (int i = 0; i < v2.size(); i++) {
		int pos1 = lower_bound(v1.begin(), v1.end(), v2[i]) - v1.begin();
		c1[dep] += 1LL * pos1;
		c2[dep] += 1LL * ((m - l) - pos1);
	}
	
	dfs(l, m, dep + 1);
	dfs(m, r, dep + 1);
}

void rollback() {
	for (int j = 0; j < (1 << N); j++) {
		if (j % 2 == 0) B[j / 2] = A[j];
		if (j % 2 == 1) B[(j / 2) + (1 << (N - 1))] = A[j];
	}
	for (int j = 0; j < (1 << N); j++) A[j] = B[j];
}

int main() {
	// Step #1. Input
	scanf("%d", &N);
	for (int i = 0; i < (1 << N); i++) scanf("%d", &A[i]);
	
	// Step #2. Initialize
	long long Answer = (1LL << 60);
	if (N == 0LL) Answer = 0;
	string AnswerLen = "";
	
	// Step #3. Calc
	for (int i = 0; i <= N - 1; i++) {
		for (int j = 0; j < N; j++) { c1[j] = 0; c2[j] = 0; }
		dfs(0, (1 << N), 0);
		long long sum = 0;
		for (int j = 0; j < N; j++) sum += min(c1[j], c2[j]);
		if (Answer > sum) {
			Answer = sum;
			string str = "";
			for (int j = 0; j < i; j++) str += "2";
			for (int j = 0; j < N; j++) {
				str += "2";
				if (c1[N - 1 - j] < c2[N - 1 - j]) str += "1";
			}
			AnswerLen = str;
		}
		//for (int j = 0; j < N; j++) cout << "#" << c1[j] << " " << c2[j] << endl;
		//cout << endl;
		rollback();
	}
	cout << Answer << endl;
	cout << AnswerLen << endl;
	return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'void dfs(int, int, int)':
cheerleaders.cpp:16:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i = 0; i < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~
cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:36:10: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   36 |  scanf("%d", &N);
      |         ~^   ~~
      |          |   |
      |          |   long long int*
      |          int*
      |         %lld
cheerleaders.cpp:37:45: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   37 |  for (int i = 0; i < (1 << N); i++) scanf("%d", &A[i]);
      |                                            ~^   ~~~~~
      |                                             |   |
      |                                             |   long long int*
      |                                             int*
      |                                            %lld
cheerleaders.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
cheerleaders.cpp:37:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  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: 0 / 28