oj.uz

답안 #753715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753715 2023-06-05T18:20:16 Z Stickfish Cheerleaders (info1cup20_cheerleaders) C++17
72 / 100
 613 ms 5436 KB 
#include <iostream>
#include <vector>
#include <cassert>
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;
}

ll get_inv_block(vector<int>::iterator begin, vector<int>::iterator end) {
    int n = end - begin;
    auto mid = begin + n / 2;
    vector<int> cless(n, 0);
    for (auto it = mid; it < end; ++it) {
        ++cless[*it];
    }
    for (int i = 1; i < n; ++i)
        cless[i] += cless[i - 1];
    ll ans = 0;
    for (auto it = begin; it < mid; ++it) {
        ans += cless[*it];
    }
    return ans;
}

void split_into_halves(vector<int>::iterator begin, vector<int>::iterator end) {
    int n = end - begin;
    auto mid = begin + n / 2;
    vector<int> pos0(n, 0);
    vector<int> pos1(n, 0);
    for (auto it = begin; it < end; ++it) {
        if (it < mid)
            ++pos0[*it];
        else
            ++pos1[*it];
    }
    --pos0[0];
    --pos1[0];
    for (int i = 1; i < n; ++i) {
        pos0[i] += pos0[i - 1];
        pos1[i] += pos1[i - 1];
    }
    for (auto it = begin; it < end; ++it) {
        if (it < mid)
            it[0] = pos0[*it];
        else
            it[0] = pos1[*it];
    }
}

pair<ll, string> get_ans(vector<int> p) {
    int n = p.size();
    vector<int> aaa = p;
    ll ans = 0;
    int ansx = 0;
    for (int bt = n / 2; bt > 0; bt /= 2) {
        ll inv0 = 0;
        for (auto it = p.begin(); it < p.end(); it += bt * 2) {
            inv0 += get_inv_block(it, it + bt * 2);
            split_into_halves(it, it + bt * 2);
        }
        ll inv1 = (n / 2) * bt - inv0;
        if (inv1 < inv0) {
            ans += inv1;
            vector<int> op(n);
            for (int i = 0; i < n; ++i)
                op[i] = i ^ bt;
            p = combine_permutations(op, p);
            ansx += bt;
        } else {
            ans += inv0;
        }
        //int nx = ansx + bt;
    //for (int nx = 0; nx < n; ++nx) {
        //ll nans = get_inversion(np);
        //if (nans < ans) {
            //ans = nans;
            //ansx = nx;
        //}
    }
    string ansa = "";
    for (int bt = 1; bt < n; bt *= 2) {
        ansa.push_back('2');
        if (ansx & bt)
            ansa.push_back('1');
    }
    return {ans, ansa};
}

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));
    }
    op2 = reverse_permutation(op2);
    //for (int i = 0; i < m; ++i)
        //cout << op2[i] << ' ';
    //cout << endl;
    ll ans = 1ll * m * m;;
    string ansa;
    string curst = "";
    for (int t = 0; t < N; ++t) {
        auto [nans, nansa] = get_ans(p);
        if (nans < ans) {
            ans = nans;
            ansa = curst + nansa;
        }
        p = combine_permutations(op2, p);
        curst.push_back('2');
    }
    cout << ans << '\n';
    cout << ansa << '\n';
    //for (int i = 0; i < m; ++i)
        //cout << p[i] << ' ';
    //cout << endl;
    //for (auto x : ansa) {
        //if (x == '1')
            //p = combine_permutations(op1, p);
        //else
            //p = combine_permutations(op2, p);
    //}
    //for (int i = 0; i < m; ++i)
        //cout << p[i] << ' ';
    //cout << endl;
    //cout << get_inversion(p) << endl;
    //assert(get_inversion(p) == ans);
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Correct!
2 Correct 1 ms 212 KB Correct!
3 Correct 0 ms 212 KB Correct!
4 Correct 0 ms 212 KB Correct!

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Correct!
2 Correct 1 ms 212 KB Correct!
3 Correct 1 ms 212 KB Correct!
4 Correct 1 ms 212 KB Correct!

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 340 KB Correct!
2 Correct 6 ms 340 KB Correct!
3 Correct 7 ms 340 KB Correct!
4 Correct 6 ms 340 KB Correct!

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 1584 KB Correct!
2 Correct 120 ms 1740 KB Correct!
3 Correct 261 ms 3348 KB Correct!

Subtask #5
0.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 613 ms 5436 KB Wrong number of inversions
2 Halted 0 ms 0 KB -