Submission #1146546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146546		saidpon	Cheerleaders (info1cup20_cheerleaders)	C++20	26 / 100	2097 ms	79696 KiB

cheerleaders

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define nemeshay ios_base::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
#define int long long
#define sigma signed
#define pb push_back
#define fr first
#define sc second
#define pii pair<int, int>
#define double long double
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define OK cout << "OK" << endl
#define Ok cout << "Ok" << endl
#define nosolve cout << "-1" << endl
using namespace std;
using namespace __gnu_pbds;
const int N = 5e2 + 2, inf = 1e18 + 7, mod = 998244353;
sigma main() {
    nemeshay
    string sans = "";
    int n, logn, ans = inf;
    cin >> n;
    logn = n;
    n = (1 << n);
    vector <int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    queue <pair<pair<string, int>, vector<int>>> pon;
    pon.push({{"", 0}, a});
    while (pon.size()) {
        string s = pon.front().fr.fr;
        int cnt = pon.front().fr.sc;
        vector <int> v = pon.front().sc;
        pon.pop();
        if (cnt <= logn * 2) {
            vector <int> newv;
            for (int i = n / 2; i < n; i++) newv.pb(v[i]);
            for (int i = 0; i < n / 2; i++) newv.pb(v[i]);
            pon.push({{s + '1', cnt + 1}, newv});
            newv.clear();
            for (int i = 0; i < n; i += 2) newv.pb(v[i]);
            for (int i = 1; i < n; i += 2) newv.pb(v[i]);
            pon.push({{s + '2', cnt + 1}, newv});
        }
        int sum = 0;
        ordered_set ok;
        for (int i = 0; i < n; i++) {
            sum += v[i] - ok.order_of_key(v[i]);
            ok.insert(v[i]);
        }
        if (ans > sum) ans = sum, sans = s;
    }
    if (sans.empty()) sans = '1';
    cout << ans << endl << sans;
}

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