oj.uz

답안 #429508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429508 2021-06-16T04:33:18 Z lyc Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 201 ms 10836 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;

int N, n, A[1<<17], B[1<<17], cnt[18][1<<17];
ll inc[17][2];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    n = (1<<N);
    FOR(i,0,n-1){
        int B; cin >> B;
        A[B] = i;
    }

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

    ll ans = 1e18;
    int mini = -1, bits = -1;
    FOR(i,0,N-1){
        memset(inc,0,sizeof inc);
        memset(cnt,0,sizeof cnt);
        FOR(j,0,n-1){
            A[j] = (A[j]>>1) | ((A[j]&1)<<(N-1));
            int B = A[j];
            FOR(k,0,N-1){
                inc[k][B&1] += cnt[N-k-1][B>>1] - cnt[N-k][B];
                cnt[N-k][B]++;
                B >>= 1;
            }
            ++cnt[0][0];
        }

        //FOR(j,0,n-1){ cout << A[j] << ' '; } cout << endl;
        //FOR(k,0,N-1){ cout << k _ inc[k][0] _ inc[k][1] << endl; }

        ll cur = 0;
        int x = 0;
        FOR(j,0,N-1){
            if (inc[j][0] < inc[j][1]) cur += inc[j][0];
            else cur += inc[j][1], x |= (1<<j);
        }
        if (cur < ans) ans = cur, mini = i, bits = x;
    }
    cout << ans << '\n';
    FOR(i,0,mini) cout << 2;
    FOR(i,0,N-1){
        cout << 2;
        if (bits&(1<<i)) cout << 1;
    }
    cout << '\n';
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Correct!
2 Correct 10 ms 9548 KB Correct!
3 Correct 9 ms 9548 KB Correct!
4 Correct 7 ms 9548 KB Correct!

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 9564 KB Correct!
2 Correct 17 ms 9560 KB Correct!
3 Correct 18 ms 9548 KB Correct!
4 Correct 18 ms 9548 KB Correct!

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 9676 KB Correct!
2 Correct 50 ms 9548 KB Correct!
3 Correct 88 ms 9788 KB Correct!

Subtask #5
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 10048 KB Correct!
2 Correct 163 ms 10836 KB Correct!
3 Correct 193 ms 10828 KB Correct!
4 Correct 190 ms 10808 KB Correct!
5 Correct 201 ms 10828 KB Correct!