Submission #591994

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

messy

#include <bits/stdc++.h>
#include "messy.h"
#include <vector>
using namespace std;
 
vector<int> restore_permutation(int n, int w, int r) {
    vector <int> p (n);
    auto pre = [&] (int l, int r, auto &&pre) {
        if (l >= r) return;
        int mid = (l + r) / 2;
        string s(n, '0');
        for (int i = l; i <= r; i++){
            s[i] = '1';
        }
        for (int i = l; i <= mid; i++){
            s[i] = '0';
            add_element(s);
            s[i] = '1';
        }
        pre(l, mid, pre);
        pre(mid + 1, r, pre);
    };
    pre(0, n - 1, pre);
    compile_set();
    auto solve = [&] (int l, int r, vector <int> ps, auto &&solve) {
        if (ps.size() == 1) return;
        int mid = (l + r) / 2;
        string s(n, '0');
        vector <int> a,b;
        for (int i: ps) s[i] = '1';
        for (int i: ps) {
            s[i] = '0';
            if (check_element(s)) a.push_back(i);
            else b.push_back(i), p[i]+=ps.size() / 2;
            s[i] = '1';
        }
        solve(l, mid, a, solve);
        solve(mid + 1, r, b, solve);
    };
    vector <int> v;
    for (int i = 0; i < n; i++) v.push_back(i);
    solve(0, n-1, v, solve);
    return p;
}

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