Submission #675828

#	Time	Username	Problem	Language	Result	Execution time	Memory
675828		hotboy2703	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	1218 ms	4180 KiB

cheerleaders

#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define BIT(mask,i) (((mask) >> (i)) & 1LL)
#define MASK(i) (1LL<<(i))
long long h[200100];
long long n;
long long a[200100];
long long BIT[(1LL<<17) + 5];
void update(long long x,long long val){
    for (;x<=(1LL<<17);x+=x&-x)BIT[x]+=val;
}
long long get(long long x){
    long long res = 0;
    for (;x > 0;x -= x &-x)res += BIT[x];
    return res;
}
pair <long long,long long> solve(){
    long long res = 0;
    long long id = 0;
    for (long long i = n - 1LL;i >= 0;i --){
        long long inversion = 0;
        for (long long j = 0;j < (1LL<<(n-1LL-i));j ++){
            for (long long k = 0;k < (1LL<<i);k ++){
                update(a[(j<<(i+1LL)) + (1LL<<i) + k] + 1LL,1LL);
            }
            for (long long k = 0;k < (1LL<<i);k ++){
                inversion += get(a[(j<<(i+1LL)) + k]);
            }
            for (long long k = 0;k < (1LL<<i);k ++){
                update(a[(j<<(i+1LL)) + (1<<i) + k] + 1LL,-1LL);
            }
        }
        if ((1LL<<(n-1LL+i)) - inversion < inversion){
            id ^= (1LL<<i);
        }
        res += min((1LL<<(n-1LL+i)) - inversion , inversion);
    }
    return {res,id};
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    //freopen("DUMB.INP","r",stdin);
    //freopen("DUMB.out","w",stdout);
    cin>>n;
    for (long long i = 0;i < (1LL<<n);i ++)cin>>h[i];
    if (n == 0){
        cout<<0<<'\n';
        return 0;
    }
    long long ans = LLONG_MAX;
    pair <long long, long long> trace;
    for (long long i = n - 1LL;i >= 0;i --){
        for (long long mask = 0;mask < MASK(n);mask++){
            long long cur = i;
            long long real_mask = 0;
            for (long long k = n - 1LL;k >= 0;k --){
                real_mask ^= (BIT(mask,k)<<cur);
                cur--;
                if (cur < 0)cur = n - 1LL;
            }
            a[mask] = h[real_mask];
        }
        pair <long long,long long> tmp = solve();
        if (tmp.first < ans){
            ans = tmp.first;
            trace.first = i;
            trace.second = tmp.second;
        }
    }
    cout<<ans<<'\n';
    for (long long i = 0;i < (trace.first - n + 1LL + n) % n;i++)cout<<2;
    int cur = n - 1LL;

    for (long long i = n - 1LL;i >= 0;i--){
        if (BIT(trace.second,cur))cout<<1LL;
        cout<<2;
        cur ++;
        cur %= n;
    }
    return 0;
}

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