Submission #290204

#	Time	Username	Problem	Language	Result	Execution time	Memory
290204		Kastanda	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 100	3 ms	512 KiB

messy

// M
#include<bits/stdc++.h>
#include "messy.h"
using namespace std;
const int N = 149;
int n, P[N];
void Solve(int l, int r)
{
        if (r - l < 2)
                return ;

        string s(n, '1');
        for (int i = l; i < r; i ++)
                s[i] = '0';

        int md = (l + r) >> 1;
        for (int i = l; i < md; i ++)
                s[i] = '1', add_element(s), s[i] = '0';
        Solve(l, md);
        Solve(md, r);
}
void Restore(int l, int r, vector < int > V)
{
        assert((int)V.size() == r - l);
        if (r - l == 1)
                return void(P[l] = V[0]);

        string s(n, '1');
        for (int i : V)
                s[i] = '0';

        int md = (l + r) >> 1;
        vector < int > L, R;
        for (int i : V)
        {
                s[i] = '1';
                if (check_element(s))
                        L.push_back(i);
                else
                        R.push_back(i);
                s[i] = '0';
        }
        Restore(l, md, L);
        Restore(md, r, R);

}
vector < int > restore_permutation(int _n, int w, int r)
{
        n = _n;
        Solve(0, n);
    compile_set();
        vector < int > V;
        for (int i = 0; i < n; i ++)
                V.push_back(i);
        Restore(0, n, V);
        vector < int > Rs(n);
        for (int i = 0; i < n; i ++)
                Rs[P[i]] = i;
        return Rs;
}

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