Submission #299702

#	Time	Username	Problem	Language	Result	Execution time	Memory
299702		E869120	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	1541 ms	8548 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, vector<pair<int, int>> v) {
	if (r - l == 1) return;
	
	int m = (l + r) / 2;
	vector<pair<int, int>> v1, v2;
	for (int i = 0; i < v.size(); i++) {
		if (v[i].second < m) v1.push_back(v[i]);
		if (v[i].second >= m) v2.push_back(v[i]);
	}
	int pos1 = 0;
	for (int i = 0; i < v2.size(); i++) {
		while (pos1 < v1.size() && v1[pos1].first < v2[i].first) pos1++;
		c1[dep] += 1LL * pos1;
		c2[dep] += 1LL * ((m - l) - pos1);
	}
	
	dfs(l, m, dep + 1, v1);
	dfs(m, r, dep + 1, v2);
}

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++) {
		vector<pair<int, int>> vec;
		for (int i = 0; i < (1 << N); i++) vec.push_back(make_pair(A[i], i));
		sort(vec.begin(), vec.end());
		for (int j = 0; j < N; j++) { c1[j] = 0; c2[j] = 0; }
		dfs(0, (1 << N), 0, vec);
		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, std::vector<std::pair<int, int> >)':
cheerleaders.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
cheerleaders.cpp:18:20: 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 < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~
cheerleaders.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   while (pos1 < v1.size() && v1[pos1].first < v2[i].first) pos1++;
      |          ~~~~~^~~~~~~~~~~
cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:38:10: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   38 |  scanf("%d", &N);
      |         ~^   ~~
      |          |   |
      |          |   long long int*
      |          int*
      |         %lld
cheerleaders.cpp:39:45: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   39 |  for (int i = 0; i < (1 << N); i++) scanf("%d", &A[i]);
      |                                            ~^   ~~~~~
      |                                             |   |
      |                                             |   long long int*
      |                                             int*
      |                                            %lld
cheerleaders.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
cheerleaders.cpp:39:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  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