Submission #1100736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100736		Kirill22	Cheerleaders (info1cup20_cheerleaders)	C++17	100 / 100	1200 ms	1996 KiB

cheerleaders

#include "bits/stdc++.h"

using namespace std;

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];
    }
    if (n == 1) {
        cout << 0 << '\n' << '\n';
        return;
    }
    long long ans = (long long) 1e18;
    string answer = "";
    for (int iter = 1; 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;
        vector<int> bits;
        for (int len = 1, bit = 0; len <= n / 2; len *= 2, bit++) {
            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++) {
                    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);
            if (R < L) {
                bits.push_back((bit + iter) % k);
            }
        }
        int cur = k - 1;
        string result = "";
        auto go = [&] (int bit) {
            while (cur != bit) {
                result.push_back('2');
                cur = (cur + 1) % k;
            }
        };
        for (auto bit : bits) {
            go(bit);
            result.push_back('1');
        }
        go((k - 1 + iter) % k);
        if (ans > res) {
            ans = res;
            answer = result;
        }
    }
    cout << ans << '\n' << answer << '\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();
    }
}

• Subtask 1: 16 / 16
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28