Submission #299687

#	Time	Username	Problem	Language	Result	Execution time	Memory
299687		E869120	Cheerleaders (info1cup20_cheerleaders)	C++14	33 / 100	2074 ms	1280 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;
	for (int i = l; i < m; i++) {
		for (int j = m; j < r; j++) {
			if (A[i] < A[j]) c1[dep] += 1;
			if (A[i] > A[j]) c2[dep] += 1;
		}
	}
	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 = "1";
	
	// 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[j] > c2[j]) str += "1";
			}
			AnswerLen = str;
		}
		rollback();
	}
	cout << Answer << endl;
	cout << AnswerLen << endl;
	return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:32:10: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   32 |  scanf("%d", &N);
      |         ~^   ~~
      |          |   |
      |          |   long long int*
      |          int*
      |         %lld
cheerleaders.cpp:33:45: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   33 |  for (int i = 0; i < (1 << N); i++) scanf("%d", &A[i]);
      |                                            ~^   ~~~~~
      |                                             |   |
      |                                             |   long long int*
      |                                             int*
      |                                            %lld
cheerleaders.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
cheerleaders.cpp:33:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  for (int i = 0; i < (1 << N); i++) scanf("%d", &A[i]);
      |                                     ~~~~~^~~~~~~~~~~~~

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