Submission #418344

#	Time	Username	Problem	Language	Result	Execution time	Memory
418344		dolphingarlic	Cheerleaders (info1cup20_cheerleaders)	C++14	21 / 100	376 ms	1356 KiB

cheerleaders

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, h[1 << 17], at[1 << 17];
ll bit[(1 << 17) + 1];

void ins(int pos) {
    for (; pos <= (1 << n); pos += pos & -pos) bit[pos]++;
}

ll query(int pos) {
    ll ans = 0;
    for (; pos; pos -= pos & -pos) ans += bit[pos];
    return ans;
}

ll check(int mask, int shift) {
    memset(bit, 0, sizeof bit);
    ll ans = 0;
    for (int i = (1 << n) - 1; ~i; i--) {
        int masked = at[i] ^ mask;
        masked = (masked >> shift) + ((masked & ((1 << shift) - 1)) << (n - shift));
        ans += query(masked + 1);
        ins(masked + 1);
    }
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < (1 << n); i++) {
        cin >> h[i];
        at[h[i]] = i;
    }

    if (n <= 11) {
        ll mn = LLONG_MAX;
        string best_seq;
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int shift : {0, n - 1}) {
                int pot = check(mask, shift);
                if (pot < mn) {
                    string seq;
                    for (int i = 0; i < n; i++) {
                        seq += "2";
                        if (mask & (1 << i)) seq += "1";
                    }
                    for (int i = 0; i < shift; i++) seq += "2";
                    mn = pot;
                    best_seq = seq;
                }
            }
        }
        cout << mn << '\n' << best_seq;
    } else {
        cout << 0 << '\n';
        for (int i = 0; i < n; i++) {
            cout << 2;
            if (at[0] & (1 << i)) cout << 1;
        }
        for (int j = 0; j < __builtin_ctz(at[0] ^ at[1]); j++)
            cout << 2;
    }
    return 0;
}

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