oj.uz

Submission #388612

# Submission time Handle Problem Language Result Execution time Memory
388612 2021-04-12T09:07:46 Z warner1129 Cheerleaders (info1cup20_cheerleaders) C++17
100 / 100
 820 ms 3656 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

const int maxn = 17;

pair<long long, long long> cnt[maxn];
long long ans = 0x3f3f3f3f3f3f3f;
int opt = 0, h = 0;
int n;

void dfs(int d, vector<int> vec) {
	long long c0, c1, t0, t1;
	vector<int> L, R;
	c0 = c1 = t0 = t1 = 0;
	for (int v : vec) {
		if ((v>>d) & 1) c1++, t1 += c0, R.emplace_back(v);
		else c0++, t0 += c1, L.emplace_back(v);
	}
	cnt[d].ff += t0, cnt[d].ss += t1;
	if (d--) dfs(d, L), dfs(d, R);
}

void solve() {
	cin >> n;
	ans = 1ll * (1<<n) * ((1<<n)-1) / 2;
	vector<int> vec(1<<n);
	for (int i = 0, x; i < 1<<n; i++)
		cin >> x, vec[x] = i;
	long long cntmp = 0, optmp = 0;
	for (int i = 0; i < n; i++) {
		dfs(n-1, vec);
		cntmp = optmp = 0;
		for (int j = 0; j < n; j++) {
			if (cnt[j].ff > cnt[j].ss)
				cntmp += cnt[j].ss, optmp |= (1<<((j+i)%n));
			else cntmp += cnt[j].ff;
			cnt[j] = {0, 0};
		}
		if (cntmp < ans) ans = cntmp, opt = optmp, h = i;
		for (int j = 0; j < 1<<n; j++)
			vec[j] = (vec[j]>>1) | ((vec[j]&1)<<(n-1));	
	}
	string str;
	for (int i = 0; i < n; i++) {
		str.push_back('2');
		if ((opt>>i)&1) str.push_back('1');
	}
	while (h--) str.push_back('2');
	cout << ans << '\n' << str << '\n';
}

signed main() {
	solve();
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct!
2 Correct 0 ms 204 KB Correct!
3 Correct 1 ms 204 KB Correct!
4 Correct 0 ms 204 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct!
2 Correct 1 ms 204 KB Correct!
3 Correct 1 ms 204 KB Correct!
4 Correct 1 ms 204 KB Correct!

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Correct!
2 Correct 8 ms 340 KB Correct!
3 Correct 8 ms 332 KB Correct!
4 Correct 7 ms 332 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 1076 KB Correct!
2 Correct 120 ms 972 KB Correct!
3 Correct 310 ms 1832 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 3372 KB Correct!
2 Correct 593 ms 3656 KB Correct!
3 Correct 788 ms 3520 KB Correct!
4 Correct 804 ms 3632 KB Correct!
5 Correct 820 ms 3608 KB Correct!