| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 388585 | warner1129 | Cheerleaders (info1cup20_cheerleaders) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int maxn = 19;
pair<long long, long long> cnt[maxn];
int pos[1<<maxn];
long long ans = 0x3f3f3f3f3f3f3f;
int opt = 0, h = 0;
int n;
void dfs(int d, vector<int> vec) {
if (vec.empty() || d == -1) return;
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;
dfs(d-1, L), dfs(d-1, R);
}
void solve() {
int x;
cin >> n;
for (int i = 0; i < 1<<n; i++)
cin >> x, pos[x] = i;
vector<int> vec(1<<n), tmp(n);
long long cntmp = 0, optmp = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 1<<n; j++) vec[j] = pos[j];
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++)
pos[j] = (pos[j]>>1) | ((pos[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;
}
// 4
/