Submission #418399

#	Time	Username	Problem	Language	Result	Execution time	Memory
418399		dolphingarlic	Cheerleaders (info1cup20_cheerleaders)	C++14	33 / 100	2080 ms	3008 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) {
    fill_n(bit + 1, 1 << n, 0);
    ll ans = 0;
    for (int i = (1 << n) - 1; ~i; i--) {
        ans += query((at[i] ^ mask) + 1);
        ins((at[i] ^ mask) + 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;
    }

    ll mn = LLONG_MAX;
    string best_seq;
    for (int shift = 0; shift < max(1, n); shift++) {
        int mask = 0;
        ll inv_tot = 0;
        for (int i = n - 1; ~i; i--) {
            ll inv_0 = 0, inv_1 = 0;
            for (int j = 0; j < (1 << n); j += 1 << i + 1) {
                vector<int> left, right;
                for (int k = j; k < j + (1 << i); k++) left.push_back(h[k]);
                for (int k = j + (1 << i); k < j + (1 << i + 1); k++) right.push_back(h[k]);
                sort(left.begin(), left.end());
                sort(right.begin(), right.end());

                for (int j : left)
                    inv_0 += lower_bound(right.begin(), right.end(), j) - right.begin();
                for (int j : right)
                    inv_1 += lower_bound(left.begin(), left.end(), j) - left.begin();
            }
            if (inv_0 > inv_1) mask += 1 << i;
            inv_tot += min(inv_0, inv_1);
        }

        if (inv_tot < 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 = inv_tot;
            best_seq = seq;
        }

        for (int i = 0; i < (1 << n); i++) {
            at[i] = (at[i] >> 1) + ((at[i] & 1) << n - 1);
            h[at[i]] = i;
        }
    }
    cout << mn << '\n' << best_seq;
    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:43:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   43 |             for (int j = 0; j < (1 << n); j += 1 << i + 1) {
      |                                                     ~~^~~
cheerleaders.cpp:46:60: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   46 |                 for (int k = j + (1 << i); k < j + (1 << i + 1); k++) right.push_back(h[k]);
      |                                                          ~~^~~
cheerleaders.cpp:71:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   71 |             at[i] = (at[i] >> 1) + ((at[i] & 1) << n - 1);
      |                                                    ~~^~~

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