oj.uz

Submission #354233

# Submission time Handle Problem Language Result Execution time Memory
354233 2021-01-21T15:14:09 Z valerikk Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 971 ms 3888 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 17;

int n, h[1 << N];
int hcopy[1 << N];
int to[1 << N];
long long res[N];
string str[N];
long long bres[N][2];

vector<int> solve(int dep, int l, int r) {
    if (r - l == 1)
        return {h[l]};
    int mid = (l + r) >> 1;
    auto a = solve(dep - 1, l, mid);
    auto b = solve(dep - 1, mid, r);
    int sza = a.size(), szb = b.size();
    int i = 0;
    for (int &x : a) {
        while (i < szb && b[i] < x)
            ++i;
        bres[dep][0] += i;
    }
    i = 0;
    for (int &x : b) {
        while (i < sza && a[i] < x)
            ++i;
        bres[dep][1] += i;
    }
    vector<int> c;
    merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
    return c;
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < (1 << n); ++i)
        cin >> h[i];
    for (int i = 0; i < (1 << n); ++i)
        to[i] = i;
    for (int shift = 1; shift <= n; ++shift) {
        for (int i = 0; i < (1 << n); ++i)
            to[i] = (to[i] >> 1) + (1 << (n - 1)) * (to[i] & 1);
        memcpy(hcopy, h, sizeof(h));
        for (int i = 0; i < (1 << n); ++i)
            h[to[i]] = hcopy[i];
        for (int i = 0; i < n; ++i)
            bres[i][0] = bres[i][1] = 0;
        solve(n - 1, 0, (1 << n));
        int xr = 0;
        for (int i = 0; i < n; ++i) {
            if (bres[i][0] > bres[i][1]) {
                xr ^= (1 << i);
                res[shift % n] += bres[i][1];
            } else
                res[shift % n] += bres[i][0];
        }
        str[shift % n] = "";
        for (int i = 0; i < n; ++i) {
            int pos = (n - 1 + i) % n;
            if ((xr >> pos) & 1)
                str[shift % n].push_back('1');
            str[shift % n].push_back('2');
        }
        memcpy(h, hcopy, sizeof(h));
    }
    int shift = 0;
    for (int i = 1; i < n; ++i) {
        if (res[i] < res[shift])
            shift = i;
    }
    cout << res[shift] << endl;
    for (int i = 0; i < shift; ++i)
        cout << 2;
    cout << str[shift] << endl;
    return 0;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1388 KB Correct!
2 Correct 10 ms 1388 KB Correct!
3 Correct 9 ms 1388 KB Correct!
4 Correct 9 ms 1388 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 2024 KB Correct!
2 Correct 95 ms 2028 KB Correct!
3 Correct 233 ms 3068 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 3888 KB Correct!
2 Correct 521 ms 3572 KB Correct!
3 Correct 963 ms 3544 KB Correct!
4 Correct 969 ms 3568 KB Correct!
5 Correct 971 ms 3556 KB Correct!