Submission #354233

#	Time	Username	Problem	Language	Result	Execution time	Memory
354233		valerikk	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	971 ms	3888 KiB

cheerleaders

#include <bits/stdc++.h>

using namespace std;

const int N = 17;

int n, h[1 << N];
int hcopy[1 << N];
int to[1 << N];
long long res[N];
string str[N];
long long bres[N][2];

vector<int> solve(int dep, int l, int r) {
    if (r - l == 1)
        return {h[l]};
    int mid = (l + r) >> 1;
    auto a = solve(dep - 1, l, mid);
    auto b = solve(dep - 1, mid, r);
    int sza = a.size(), szb = b.size();
    int i = 0;
    for (int &x : a) {
        while (i < szb && b[i] < x)
            ++i;
        bres[dep][0] += i;
    }
    i = 0;
    for (int &x : b) {
        while (i < sza && a[i] < x)
            ++i;
        bres[dep][1] += i;
    }
    vector<int> c;
    merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
    return c;
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < (1 << n); ++i)
        cin >> h[i];
    for (int i = 0; i < (1 << n); ++i)
        to[i] = i;
    for (int shift = 1; shift <= n; ++shift) {
        for (int i = 0; i < (1 << n); ++i)
            to[i] = (to[i] >> 1) + (1 << (n - 1)) * (to[i] & 1);
        memcpy(hcopy, h, sizeof(h));
        for (int i = 0; i < (1 << n); ++i)
            h[to[i]] = hcopy[i];
        for (int i = 0; i < n; ++i)
            bres[i][0] = bres[i][1] = 0;
        solve(n - 1, 0, (1 << n));
        int xr = 0;
        for (int i = 0; i < n; ++i) {
            if (bres[i][0] > bres[i][1]) {
                xr ^= (1 << i);
                res[shift % n] += bres[i][1];
            } else
                res[shift % n] += bres[i][0];
        }
        str[shift % n] = "";
        for (int i = 0; i < n; ++i) {
            int pos = (n - 1 + i) % n;
            if ((xr >> pos) & 1)
                str[shift % n].push_back('1');
            str[shift % n].push_back('2');
        }
        memcpy(h, hcopy, sizeof(h));
    }
    int shift = 0;
    for (int i = 1; i < n; ++i) {
        if (res[i] < res[shift])
            shift = i;
    }
    cout << res[shift] << endl;
    for (int i = 0; i < shift; ++i)
        cout << 2;
    cout << str[shift] << endl;
    return 0;
}

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