제출 #524112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524112		LucaIlie	Cheerleaders (info1cup20_cheerleaders)	C++17	33 / 100	2070 ms	1808 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];
vector <int> ans;
AIB f;

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++ ) {
        nrInv = 0;
        for ( i = 0; i < (1 << n); i++ ) {
            nrInv += i - f.query( p[i] );
            f.update( p[i] + 1, 1 );
        }
        for ( i = 0; i < (1 << n); i++ )
            f.update( p[i] + 1, -1 );

        x = 0;
        for ( l = 0; l < n; l++ ) {
            for ( i = 0; i < (1 << n) - (1 << (l + 1)) + 1; i += (1 << (l + 1)) ) {
                for ( j = 0; j < (1 << l); j++ )
                    swap( p[i + j], p[i + j + (1 << l)] );
            }

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

            if ( newInv < nrInv ) {
                x += (1 << l);
                nrInv = newInv;
            } else {
                for ( i = 0; i < (1 << n); i += (1 << (l + 1)) ) {
                    for ( j = 0; j < (1 << l); j++ )
                        swap( p[i + j], p[i + j + (1 << l)] );
                }
            }
        }
        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 = n - 1; i >= 0; i-- ) {
        if ( (xr >> i) & 1 )
            cout << 1;
        cout << 2;
    }

    return 0;
}

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