Submission #524147

#	Time	Username	Problem	Language	Result	Execution time	Memory
524147		LucaIlie	Cheerleaders (info1cup20_cheerleaders)	C++17	72 / 100	2017 ms	2600 KiB

cheerleaders

#include <iostream>
#include <vector>

#define MAX_N 17

using namespace std;

struct AIB {
    int aib[(1 << MAX_N) + 1];

    int query( int i ) {
        int s;

        s = 0;
        while ( i > 0 ) {
            s += aib[i];
            i -= (i & -i);
        }

        return s;
    }

    void update( int i, int x ) {
        while ( i <= (1 << MAX_N) ) {
            aib[i] += x;
            i += (i & -i);
        }
    }
};

AIB f;

long long countInv( int v[], int n ) {
    int i;
    long long nrInv;

    nrInv = 0;
    for ( i = 0; i < n; i++ ) {
        nrInv += i - f.query( v[i] );
        f.update( v[i] + 1, 1 );
    }
    for ( i = 0; i < n; i++ )
        f.update( v[i] + 1, -1 );

    return nrInv;
}

int v[1 << MAX_N], p[1 << MAX_N];
long long sumInv[MAX_N + 1];
vector <int> ans;

int main() {
    int n, rot, xr, r, x, l, i, j;
    long long minInv, nrInv, newInv;

    cin >> n;
    for ( i = 0; i < (1 << n); i++ )
        cin >> p[i];

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

    minInv = (1LL << (2 * n));
    xr = rot = 0;
    for ( r = 0; r < n; r++ ) {
        for ( i = 0; i < (1 << n); i++ )
            v[i] = p[i];

        for ( l = 0; l <= n; l++ ) {
            sumInv[l] = 0;
            for ( i = 0; i < (1 << n) - (1 << l) + 1; i += (1 << l) )
                sumInv[l] += countInv( p + i, (1 << l) );
        }

        x = 0;
        nrInv = sumInv[n];
        for ( l = n - 1; l >= 0; l-- ) {
            newInv = sumInv[n] - sumInv[l + 1] + sumInv[l] + ((1LL << (l + n - 1)) - (sumInv[l + 1] - sumInv[l]));
            if ( newInv < sumInv[n] ) {
                x += (1 << l);
                nrInv -= sumInv[n] - newInv;
            }
        }

        if ( nrInv < minInv ) {
            minInv = nrInv;
            rot = r;
            xr = x;
        }

        for ( i = 0; i < (1 << n); i++ )
            v[i] = p[i];
        for ( i = 0; i < (1 << n); i++ )
            p[((i & 1) << (n - 1)) + (i >> 1)] = v[i];
    }

    cout << minInv << "\n";
    for ( i = 0; i < rot; i++ )
        cout << 2;
    for ( i = 0; i < n; i++ ) {
        cout << 2;
        if ( (xr >> i) & 1 )
            cout << 1;
    }

    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:53:33: warning: unused variable 'j' [-Wunused-variable]
   53 |     int n, rot, xr, r, x, l, i, j;
      |                                 ^

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