oj.uz

답안 #208515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208515 2020-03-11T11:48:37 Z Alexa2001 Cheerleaders (info1cup20_cheerleaders) C++17
100 / 100
 446 ms 3292 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Correct!
2 Correct 5 ms 376 KB Correct!
3 Correct 5 ms 376 KB Correct!
4 Correct 5 ms 376 KB Correct!

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Correct!
2 Correct 5 ms 376 KB Correct!
3 Correct 5 ms 376 KB Correct!
4 Correct 5 ms 376 KB Correct!

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 376 KB Correct!
2 Correct 8 ms 376 KB Correct!
3 Correct 8 ms 376 KB Correct!
4 Correct 8 ms 376 KB Correct!

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 1016 KB Correct!
2 Correct 79 ms 1016 KB Correct!
3 Correct 166 ms 1656 KB Correct!

Subtask #5
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 375 ms 3292 KB Correct!
2 Correct 365 ms 2936 KB Correct!
3 Correct 446 ms 3100 KB Correct!
4 Correct 438 ms 2936 KB Correct!
5 Correct 442 ms 3096 KB Correct!