oj.uz

Submission #365113

# Submission time Handle Problem Language Result Execution time Memory
365113 2021-02-10T22:09:40 Z Alexandruabcde Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 415 ms 19052 KB 
#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;
}

Compilation message

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.0 / 16.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Correct!
2 Correct 3 ms 620 KB Correct!
3 Correct 3 ms 620 KB Correct!
4 Correct 3 ms 620 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4620 KB Correct!
2 Correct 57 ms 4736 KB Correct!
3 Correct 146 ms 9580 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 19052 KB Correct!
2 Correct 348 ms 18924 KB Correct!
3 Correct 415 ms 19052 KB Correct!
4 Correct 402 ms 18972 KB Correct!
5 Correct 402 ms 18924 KB Correct!