Submission #753695

#	Time	Username	Problem	Language	Result	Execution time	Memory
753695		Stickfish	Cheerleaders (info1cup20_cheerleaders)	C++17	13 / 100	2069 ms	2872 KiB

cheerleaders

#include <iostream>
#include <vector>
using ll = long long;
using namespace std;

ll get_inversion(vector<int>& p) {
    int n = p.size();
    ll ans = 0;
    for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
        ans += p[i] > p[j];
    }
    return ans;
}

vector<int> combine_permutations(vector<int> a, vector<int> b) {
    int n = a.size();
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[i] = b[a[i]];
    }
    return ans;
}

vector<int> reverse_permutation(vector<int> a) {
    int n = a.size();
    vector<int> ans(n);
    for (int i = 0; i < n; ++i)
        ans[a[i]] = i;
    return ans;
}

pair<ll, string> get_ans(vector<int> p) {
    int n = p.size();
    vector<int> aaa = p;
    ll ans = get_inversion(aaa);
    int ansx = 0;
    //for (int bt = n / 2; bt > 0; bt /= 2) {
        //int nx = ansx + bt;
    for (int nx = 0; nx < n; ++nx) {
        vector<int> op(n);
        for (int i = 0; i < n; ++i)
            op[i] = i ^ nx;
        vector<int> np = combine_permutations(op, p);
        ll nans = get_inversion(np);
        if (nans < ans) {
            ans = nans;
            ansx = nx;
        }
    }
    //cout << ans << ' ' << ansx << endl;
    return {ans, "12111"};
}

signed main() {
    int N;
    cin >> N;
    int m = (1 << N);
    vector<int> p(m);
    for (int i = 0; i < m; ++i)
        cin >> p[i];
    if (N == 0) {
        cout << "0\n";
        cout << "1\n";
        return 0;
    }
    vector<int> op1(m);
    vector<int> op2(m);
    for (int i = 0; i < m; ++i) {
        op1[i] = i ^ (m / 2);
        op2[i] = (i >> 1) + ((i & 1) << (N - 1));
    }
    ll ans = 1ll * m * m;;
    string ansa;
    for (int t = 0; t < N; ++t) {
        auto [nans, nansa] = get_ans(p);
        if (nans < ans) {
            ans = nans;
            ansa = nansa;
        }
        p = combine_permutations(op2, p);
    }
    cout << ans << '\n';
    cout << ansa << '\n';

}

Compilation message (stderr)

cheerleaders.cpp: In function 'std::pair<long long int, std::__cxx11::basic_string<char> > get_ans(std::vector<int>)':
cheerleaders.cpp:36:9: warning: variable 'ansx' set but not used [-Wunused-but-set-variable]
   36 |     int ansx = 0;
      |         ^~~~

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