oj.uz

Submission #524417

# Submission time Handle Problem Language Result Execution time Memory
524417 2022-02-09T07:37:57 Z LucaIlie Cheerleaders (info1cup20_cheerleaders) C++17
100 / 100
 275 ms 2740 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct!
2 Correct 1 ms 204 KB Correct!
3 Correct 1 ms 204 KB Correct!
4 Correct 0 ms 204 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct!
2 Correct 1 ms 204 KB Correct!
3 Correct 1 ms 300 KB Correct!
4 Correct 0 ms 204 KB Correct!

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Correct!
2 Correct 2 ms 332 KB Correct!
3 Correct 3 ms 308 KB Correct!
4 Correct 2 ms 460 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 808 KB Correct!
2 Correct 23 ms 764 KB Correct!
3 Correct 47 ms 1356 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 2500 KB Correct!
2 Correct 125 ms 2740 KB Correct!
3 Correct 269 ms 2604 KB Correct!
4 Correct 259 ms 2596 KB Correct!
5 Correct 275 ms 2628 KB Correct!