Submission #429508

#	Time	Username	Problem	Language	Result	Execution time	Memory
429508		lyc	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	201 ms	10836 KiB

cheerleaders

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;

int N, n, A[1<<17], B[1<<17], cnt[18][1<<17];
ll inc[17][2];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    n = (1<<N);
    FOR(i,0,n-1){
        int B; cin >> B;
        A[B] = i;
    }

    if (N == 0) {
        cout << 0 << '\n';
        return 0;
    }

    ll ans = 1e18;
    int mini = -1, bits = -1;
    FOR(i,0,N-1){
        memset(inc,0,sizeof inc);
        memset(cnt,0,sizeof cnt);
        FOR(j,0,n-1){
            A[j] = (A[j]>>1) | ((A[j]&1)<<(N-1));
            int B = A[j];
            FOR(k,0,N-1){
                inc[k][B&1] += cnt[N-k-1][B>>1] - cnt[N-k][B];
                cnt[N-k][B]++;
                B >>= 1;
            }
            ++cnt[0][0];
        }

        //FOR(j,0,n-1){ cout << A[j] << ' '; } cout << endl;
        //FOR(k,0,N-1){ cout << k _ inc[k][0] _ inc[k][1] << endl; }

        ll cur = 0;
        int x = 0;
        FOR(j,0,N-1){
            if (inc[j][0] < inc[j][1]) cur += inc[j][0];
            else cur += inc[j][1], x |= (1<<j);
        }
        if (cur < ans) ans = cur, mini = i, bits = x;
    }
    cout << ans << '\n';
    FOR(i,0,mini) cout << 2;
    FOR(i,0,N-1){
        cout << 2;
        if (bits&(1<<i)) cout << 1;
    }
    cout << '\n';
}

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