Submission #354209

#	Time	Username	Problem	Language	Result	Execution time	Memory
354209		valerikk	Cheerleaders (info1cup20_cheerleaders)	C++11	0 / 100	106 ms	1732 KiB

cheerleaders

#include <bits/stdc++.h>

using namespace std;

long long count_inv(vector<int> &a, vector<int> &b) {
    int ptr = 0;
    long long res = 0;
    for (int &x : b) {
        while (ptr < a.size() && a[ptr] <= x)
            ++ptr;
        res += (int)a.size() - ptr;
    }
    return res;
}

const int N = 17;

int n;
int h[1 << N];
long long res[N][2];

void achieve(int mask) {
    for (int i = 0; i < n; ++i) {
        int pos = (n - 1 + i) % n;
        if ((mask >> pos) & 1) cout << 1;
        cout << 2;
    }
    cout << endl;
}

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 t = 1; t <= n; ++t) {
        for (int i = 0; i + (1 << t) <= (1 << n); i += (1 << t)) {
            vector<int> a, b;
            for (int j = 0; j < (1 << (t - 1)); ++j) {
                a.push_back(h[i + j]);
                b.push_back(h[i + j + (1 << (t - 1))]);
            }
            sort(a.begin(), a.end());
            sort(b.begin(), b.end());
            res[t - 1][0] += count_inv(a, b);
            res[t - 1][1] += count_inv(b, a);
        }
    }
    int mask = 0;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        if (res[i][0] > res[i][1])
            mask ^= (1 << i);
        ans += min(res[i][0], res[i][1]);
    }
    cout << ans << endl;
    achieve(mask);
    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'long long int count_inv(std::vector<int>&, std::vector<int>&)':
cheerleaders.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |         while (ptr < a.size() && a[ptr] <= x)
      |                ~~~~^~~~~~~~~~

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