| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1100729 | Kirill22 | Cheerleaders (info1cup20_cheerleaders) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#include "debug.h"
void solve() {
int k;
cin >> k;
int n = 1 << k;
vector<int> arr(n), f(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
long long ans = (long long) 1e18;
for (int iter = 0; iter < k; iter++) {
vector<int> a(n);
for (int i = 0; i < n; i++) {
a[i / 2 + (i % 2 ? (1 << (k - 1)) : 0)] = arr[i];
}
arr = a;
long long res = 0;
for (int len = 1; len <= n / 2; len *= 2) {
long long L = 0, R = 0;
for (int i = 0; i < n; i += len * 2) {
long long val = 0;
for (int j = i + len; j < i + len * 2; j++) {
for (int x = a[j]; x < n; x |= (x + 1)) {
f[x]++;
}
}
for (int j = i; j < i + len; j++) {
val += len;
for (int x = a[j]; x >= 0; x = (x & (x + 1)) - 1) {
val -= f[x];
}
}
for (int j = i + len; j < i + len * 2; j++) {
for (int x = a[j]; x < n; x |= (x + 1)) {
f[x]--;
}
}
L += val;
R += len * 1ll * len - val;
}
res += min(L, R);
}
ans = min(ans, res);
}
cout << ans << '\n';
// set<vector<int>> usd;
// auto dfs = [&] (auto&& self, vector<int> ord) {
// if (usd.find(ord) != usd.end()) {
// return;
// }
// usd.insert(ord);
//// if (ord[0] == 0 || ord[0] == n - 1) debug(ord);
// vector<int> a(n);
// for (int i = 0; i < n; i++) {
// if (i < n / 2) a[i] = ord[i + n / 2];
// else a[i] = ord[i - n / 2];
// }
// self(self, a);
// for (int i = 0; i < n; i++) {
// if (i < n / 2) a[i] = ord[i * 2];
// else a[i] = ord[1 + (i - n / 2) * 2];
// }
// self(self, a);
// };
// vector<int> ord(n);
// std::iota(ord.begin(), ord.end(), 0);
// dfs(dfs, ord);
// cout << usd.size();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}