Submission #482058

#	Time	Username	Problem	Language	Result	Execution time	Memory
482058		Redhood	Cheerleaders (info1cup20_cheerleaders)	C++14	33 / 100	2074 ms	2128 KiB

cheerleaders

#include<bits/stdc++.h>
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second

using namespace __gnu_pbds;
using namespace std;
using namespace __gnu_cxx;
using namespace std;

typedef long long ll;

const int N = (1 << 17) + 100;
int fen[N];
void modify(int x , int pl){
    for(; x < N; x += x & -x)
        fen[x] += pl;
}
int get(int p){
    int ans = 0;
    for(; p > 0; p -= p & -p)
        ans += fen[p];
    return ans;
}
int F = 4;
void out(vector < ll > p){
  int b;
    b = F;
    for(auto i : p){
        for(int f = b-1; f >= 0; --f){
            if((1 << f) & i)
                cout<<1;
            else cout<<0;
        }
        cout << '\n';
    }
}


ll inv(vector < int > &p){
    ll ans = 0;
    for(int i : p){
        ans += get(N - 1 - i);
        modify(N - 1 - i , +1);
    }
    for(int i : p)
        modify( N - 1 - i , -1);
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;

    if(n == 0){
        return cout << 0 , 0;
    }

    vector < int > h((1 << n));
    for(int i = 0 ;i < sz(h); ++i)
        cin >> h[i], h[i]++;


    int ANS = 0;
    ll ans = 1e18;

    vector < int > perm(n);

    iota(all(perm) , 0);
    reverse(all(perm));
    for(int it = 0; it < n; ++it){


        ll nowans = 0;
        ANS = 0;
        for(int b = 0; b < n; ++b){
            ll cur = 0;
            ll pairs = 0;
            for(int pref = 0; pref < (1 << b); ++pref){
                int msk = 0;
                for(int x = 0; x < b; ++x){
                    if((1 << x) & pref)
                        msk |= (1 << perm[x]);
                }
                vector < int > st[2];
                for(int t = 0; t < 2; ++t){
                    int curmsk = msk;
                    if(t)
                        curmsk |= (1 << perm[b]);
                    for(int suf = 0; suf < (1 << (n - 1 - b)); ++suf){

                        int nwmsk = curmsk;
                        for(int x = 0; x < (n - 1 - b); ++x){
                            if((1 << x) & suf){
                                assert(x + b - 1 < n);
                                nwmsk |= (1 << perm[x + b + 1]);
                            }
                        }
                        st[t].pb(nwmsk);
                    }
                }
                assert(sz(st[0])==sz(st[1]));

                pairs += 1ll * sz(st[0]) * sz(st[1]);
                for(auto i : st[0])
                    modify(h[i] , 1);
                for(auto j : st[1])
                    cur += get(h[j]);
                for(auto i : st[0])
                    modify(h[i] , -1);
            }
            ANS *= 2;
            if(cur < pairs-cur){
                ANS++;
            }
            nowans += min(cur , pairs - cur);
        }
//
//        if(nowans == 41){
//            cout << "WTF \n";
//            for(auto u : perm)
//                cout << u << ' ';
//            cout << endl;
//            cout << ANS << endl;
//            out({ANS});
//        }

        ans = min(ans , nowans);


        perm.insert(perm.begin(), perm.back());
        perm.pop_back();
    }



    cout << ans;

    return 0;
}

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