Submission #365091

#	Time	Username	Problem	Language	Result	Execution time	Memory
365091		Alexandruabcde	Cheerleaders (info1cup20_cheerleaders)	C++14	0 / 100	275 ms	19180 KiB

cheerleaders

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

constexpr int NMAX = 18;

LL ans = 0;
vector <int> moves;

int p[(1<<NMAX)];

int N;

LL mat[NMAX][(1<<NMAX)];

LL valbit[2][NMAX];

int BigSwap (int x) {
    return (x^(1<<(N-1)));
}

int BigSplit (int x) {
    return ((x>>1)|((x&1)<<(N-1)));
}

void Solve (int cnt_Splits) {
    for (int i = 0; i < N; ++ i )
        for (int j = 0; j < 2; ++ j )
            valbit[j][i] = 0;
    for (int i = 0; i < N; ++ i )
        for (int j = 0; j < (1<<N); ++ j )
            mat[i][j] = 0;

    for (int i = 0; i < (1<<N); ++ i ) {
        int val = p[i];

        for (int j = 0; j < N; ++ j ) {
            int bit = (val&(1<<j));

            if (bit != 0) bit = 1;

            valbit[bit][j] += mat[j][((val>>j)^1)];
        }

        for (int j = 0; j < N; ++ j )
            mat[j][(val>>j)] ++;
    }

    LL xor_val = 0,cnt_Inv = 0;
    for (int i = 0; i < N; ++ i ) {
        if (i >= N-cnt_Splits && valbit[1][i] < valbit[0][i]) {
            xor_val += (1<<i);
            cnt_Inv += 1LL * valbit[1][i];
        }
        else {
            cnt_Inv += 1LL * valbit[0][i];
        }
    }

    if (cnt_Inv < ans) {
        ans = cnt_Inv;
        moves.clear();

        for (int i = 0; i < cnt_Splits; ++ i ) {
            if (N-cnt_Splits + i >= 0 && (xor_val&(1<<i))) {
                moves.push_back(1);
            }

            moves.push_back(2);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 0; i < (1<<N); ++ i ) {
        int x;

        cin >> x;

        p[x] = i;
    }

    ans = (1LL<<(2*N));

    for (int i = 0; i <= N; ++ i ) {
        Solve(i);

        for (int j = 0; j < (1<<N); ++ j )
            p[j] = BigSplit(p[j]);
    }

    cout << ans << '\n';
    for (int i = 0; i < moves.size(); ++ i )
        cout << moves[i];

    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i < moves.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~

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