Submission #330491

#	Time	Username	Problem	Language	Result	Execution time	Memory
330491		IgorI	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	110 ms	620 KiB

messy

#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <cstdlib>
#include <iostream>
#include "messy.h"

using namespace std;

#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int (i) = 0; (i) < (n); (i)++)

void build(int l, int r, int n)
{
    if (l + 1 == r)
    {
        return;
    }
    int m = (l + r) / 2;
    for (int i = l; i < m; i++)
    {
        string s(n, '1');
        for (int j = l; j < r; j++)
            s[j] = '0';
        s[i] = '1';
        add_element(s);
    }
    build(l, m, n);
    build(m, r, n);
}

void restore(int n, vector<int> sc, int l, int r, vector<int> &ans)
{
    if (l + 1 == r)
    {
        ans[l] = sc[0];
        return;
    }
    string s(n, '1');
    for (auto e : sc)
        s[e] = '0';
    vector<int> on, off;
    for (auto e : sc)
    {
        s[e] = '1';
        if (check_element(s))
            on.push_back(e);
        else
            off.push_back(e);
        s[e] = '0';
    }
    int m = (l + r) / 2;
    restore(n, on, l, m, ans);
    restore(n, off, m, r, ans);
}

vector<int> restore_permutation(int n, int w, int r)
{
    build(0, n, n);
    compile_set();
    vector<int> ans(n);
    vector<int> sc;
    for (int i = 0; i < n; i++) sc.push_back(i);
    restore(n, sc, 0, n, ans);
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        p[ans[i]] = i;
    return p;
}

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