제출 #365113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365113		Alexandruabcde	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	415 ms	19052 KiB

cheerleaders

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

constexpr LL NMAX = 18;

LL ans = 0;
vector <LL> moves;

LL p[(1<<NMAX)];

LL N;

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

LL valbit[2][NMAX];

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

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

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

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

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

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

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

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

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

        if (N - cnt_Splits - 1 >= 0 && (xor_val&(1LL<<(N-cnt_Splits-1)))) moves.push_back(1);

        for (int i = 1; i <= cnt_Splits; ++ i  ) {
            moves.push_back(2);

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

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

    cin >> N;

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

        cin >> x;

        p[x] = i;
    }

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

    for (LL i = 0; i <= 2*N; ++ i ) {
        Solve(i);

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

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

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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