Submission #208515

#	Time	Username	Problem	Language	Result	Execution time	Memory
208515		Alexa2001	Cheerleaders (info1cup20_cheerleaders)	C++17	100 / 100	446 ms	3292 KiB

cheerleaders

#include <bits/stdc++.h>

using namespace std;


typedef long long ll;

const ll inf = 1e18;
const int Nmax = 1<<20;

int A[Nmax], P[Nmax], p[Nmax];
ll inv[22][2];
int n, N;

void print(int xor_val, int shift, ll min_inv)
{
    cout << min_inv << '\n';

    string ans;
    int i;

    for(i=0; i<shift; ++i) ans.push_back('2');

    for(i=0; i<n; ++i)
    {
        ans.push_back('2');
        if(xor_val & (1<<i)) ans.push_back('1');
    }

    cout << ans << '\n';
}

pair<ll,int> solve(int shift)
{
    int i, j;

    for(i=0; i<N; ++i)
    {
        int part1, part2;
        part1 = P[i] & ((1<<shift) - 1);
        part2 = P[i] >> shift;

        p[i] = (part1 << (n-shift)) | part2;
    }

    vector< vector<int> > cnt;
    cnt.resize(n+1);

    for(i=1; i<=n; ++i)
        cnt[i].resize(1<<i);

    memset(inv, 0, sizeof(inv));

    for(i=0; i<N; ++i)
        for(j=0; j<n; ++j)
        {
            int other = (p[i] >> j) ^ 1;

            if(other > (p[i]>>j))
                inv[j][0] += cnt[n-j][other];
            else
                inv[j][1] += cnt[n-j][other];

            cnt[n-j][p[i] >> j] ++;
        }

    int xor_val = 0;
    ll min_inv = 0;

    for(i=0; i<n; ++i)
        if(inv[i][0] < inv[i][1]) min_inv += inv[i][0];
            else min_inv += inv[i][1], xor_val |= (1<<i);

    return {min_inv, xor_val};
}

int main()
{
  //  freopen("input", "r", stdin);
   // freopen("output", "w", stdout);

    cin >> n;
    N = (1<<n);

    if(n == 0)
    {
        cout << 0 << '\n';
        exit(0);
    }

    int i;
    for(i=0; i<N; ++i) assert(cin >> A[i]);
    for(i=0; i<N; ++i) P[A[i]] = i;

    ll min_inv = inf, xor_val, shift;

    for(i=0; i<n; ++i)
    {
        pair<ll, int> res = solve(i);

        if(res.first < min_inv)
            min_inv = res.first, xor_val = res.second, shift = i;
    }

    print(xor_val, shift, min_inv);

    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:105:10: warning: 'shift' may be used uninitialized in this function [-Wmaybe-uninitialized]
     print(xor_val, shift, min_inv);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cheerleaders.cpp:105:10: warning: 'xor_val' may be used uninitialized in this function [-Wmaybe-uninitialized]

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