Submission #299699

#	Time	Username	Problem	Language	Result	Execution time	Memory
299699		E869120	Cheerleaders (info1cup20_cheerleaders)	C++14	72 / 100	2037 ms	3728 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<int> v1; for (int i = l; i < m; i++) v1.push_back(A[i]);
	vector<int> v2; for (int i = m; i < r; i++) v2.push_back(A[i]);
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	int pos1 = 0;
	for (int i = 0; i < v2.size(); i++) {
		while (pos1 < v1.size() && v1[pos1] < v2[i]) pos1++;
		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:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for (int i = 0; i < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~
cheerleaders.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   while (pos1 < v1.size() && v1[pos1] < v2[i]) pos1++;
      |          ~~~~~^~~~~~~~~~~
cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:37:10: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   37 |  scanf("%d", &N);
      |         ~^   ~~
      |          |   |
      |          |   long long int*
      |          int*
      |         %lld
cheerleaders.cpp:38:45: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   38 |  for (int i = 0; i < (1 << N); i++) scanf("%d", &A[i]);
      |                                            ~^   ~~~~~
      |                                             |   |
      |                                             |   long long int*
      |                                             int*
      |                                            %lld
cheerleaders.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
cheerleaders.cpp:38:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  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