oj.uz

답안 #299702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299702 2020-09-15T13:22:58 Z E869120 Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 1541 ms 8548 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 223 ms 2172 KB Correct!
2 Correct 227 ms 2176 KB Correct!
3 Correct 522 ms 4132 KB Correct!

Subtask #5
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1095 ms 7724 KB Correct!
2 Correct 1111 ms 7800 KB Correct!
3 Correct 1512 ms 7684 KB Correct!
4 Correct 1524 ms 8356 KB Correct!
5 Correct 1541 ms 8548 KB Correct!