Submission #1121870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121870		Nelt	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	764 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
ll n;
vector<int> ans;
void init(ll l, ll r)
{
    if (l == r) return;
    string s(n, '1');
    ll mid = (l + r) >> 1;
    for (ll i = l; i <= r; i++) s[i] = '0';
    for (ll i = l; i <= mid; i++) s[i] = '1', add_element(s), s[i] = '0';
    init(l, mid);
    init(mid + 1, r);
}
void solve(ll bit, vector<ll> v)
{
    if (bit == 0) return;
    string s(n, '1');
    for (ll i : v) s[i] = '0';
    vector<ll> vl, vr;
    for (ll i : v)
    {
        s[i] = '1';
        if (!check_element(s)) vr.push_back(i), ans[i] |= bit;
        else vl.push_back(i);
        s[i] = '0';
    }
    solve(bit >> 1, vl);
    solve(bit >> 1, vr);
}
std::vector<int> restore_permutation(int N, int w, int r) {
    n = N;
    ans.assign(n, 0);
    init(0, n - 1);
    compile_set();
    vector<ll> v;
    for (ll i = 0; i < n; i++) v.push_back(i);
    solve(n >> 1, v);
    return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30