Submission #524417

#	Time	Username	Problem	Language	Result	Execution time	Memory
524417		LucaIlie	Cheerleaders (info1cup20_cheerleaders)	C++17	100 / 100	275 ms	2740 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);
        }
    }
};

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

long long countInv( int v[], int l, int r, int len ) {
    int mid, i, j, p;
    long long nrInv;

    if ( l == r )
        return 0;

    mid = (l + r) / 2;
    nrInv = countInv( v, l, mid, len - 1 ) + countInv( v, mid + 1, r, len - 1 );

    i = l;
    j = mid + 1;
    p = 0;
    while ( i <= mid && j <= r ) {
        if ( v[i] < v[j] ) {
            aux[p] = v[i];
            i++;
        } else {
            aux[p] = v[j];
            j++;
            nrInv += mid - i + 1;
        }
        p++;
    }
    while ( i <= mid ) {
        aux[p] = v[i];
        i++;
        p++;
    }
    while ( j <= r ) {
        aux[p] = v[j];
        j++;
        p++;
        nrInv += mid - i + 1;
    }

    sumInv[len] += nrInv;

    for ( i = l; i <= r; i++ )
        v[i] = aux[i - l];

    return nrInv;
}


int main() {
    int n, rot, xr, r, x, l, i;
    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;

        countInv( v, 0, (1 << n) - 1, n );

        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;
}

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