oj.uz

Submission #482057

# Submission time Handle Problem Language Result Execution time Memory
482057 2021-10-22T20:39:56 Z Redhood Cheerleaders (info1cup20_cheerleaders) C++14
33 / 100
 18 ms 2892 KB 
#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;
}
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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct!
2 Correct 0 ms 204 KB Correct number of inversions, wrong sequence of operations
3 Correct 0 ms 332 KB Correct number of inversions, wrong sequence of operations
4 Correct 1 ms 204 KB Correct number of inversions, wrong sequence of operations

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct number of inversions, wrong sequence of operations
2 Correct 1 ms 204 KB Correct number of inversions, wrong sequence of operations
3 Correct 1 ms 204 KB Correct number of inversions, wrong sequence of operations
4 Correct 1 ms 204 KB Correct number of inversions, wrong sequence of operations

Subtask #3
20.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 332 KB Correct number of inversions, wrong sequence of operations
2 Correct 14 ms 332 KB Correct number of inversions, wrong sequence of operations
3 Correct 14 ms 332 KB Correct number of inversions, wrong sequence of operations
4 Correct 14 ms 332 KB Correct number of inversions, wrong sequence of operations

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 2892 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -