Submission #482056

#	Time	Username	Problem	Language	Result	Execution time	Memory
482056		Redhood	Cheerleaders (info1cup20_cheerleaders)	C++14	13 / 100	2045 ms	2508 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 << 13);
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;
}


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);
    for(int it = 0; it < n; ++it){


        for(int msk = 0; msk < (1 << n); ++msk){
            vector < int > P((1 << n));
            for(int b = 0; b < n; ++b){
                int l = (1 << perm[b]);
                int init = ((1 << b) & msk) > 0;
                for(int f = 0; f < (1 << n); f += l){
                    for(int x = f; x < f + l; ++x){
                        if(init)
                            P[x] |= (1 << b);
                    }
                    init ^= 1;
                }
            }
            for(int &x : P)
                x = h[x];
            ans = min(ans , inv(P));
        }

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



    cout << ans;

    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:55:9: warning: unused variable 'ANS' [-Wunused-variable]
   55 |     int ANS = 0;
      |         ^~~

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