제출 #1145830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145830		saidpon	Cheerleaders (info1cup20_cheerleaders)	C++20	26 / 100	2097 ms	35952 KiB

cheerleaders

#include <bits/stdc++.h>
#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;
const int N = 5e2 + 2, inf = 1e18 + 7, mod = 998244353;
sigma main() {
    nemeshay
    string sans = "";
    int n, ans = inf;
    cin >> 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 < 15) {
            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;
        for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (v[i] > v[j]) sum++;
        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