Submission #1045396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045396		fv3	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	1 ms	632 KiB

messy

#include "messy.h"

#include <bits/stdc++.h>
using namespace std;

vector<vector<set<int>>> bs;

int N;
void add_range(int l, int r)
{
    string el(N, '1');
    for (int i = l; i <= r; i++)
        el[i] = '0';

    for (int i = l; i <= (l + r) / 2; i++)
    {
        el[i] = '1';
        add_element(el);
        //cerr << el << '\n';
        el[i] = '0';
    }
}

void add_ranges(int l, int r)
{
    if (r == l) return;
    add_range(l, r);

    int c = (l + r) / 2;
    add_ranges(l, c);
    add_ranges(c+1, r);
}

void find_range(int l, int r, int layer, int index)
{
    if (r == l) return;

    string el(N, '1');
    for (int i = 0; i < N; i++)
    {
        if (bs[layer][index].count(i))
            el[i] = '0';
    }

    for (auto i : bs[layer][index])
    {
        el[i] = '1';
        //cerr << el << '\n';
        if (check_element(el))
            bs[layer+1][index*2].insert(i);
        else
            bs[layer+1][index*2|1].insert(i);

        el[i] = '0';
    }

    int c = (l + r) / 2;
    find_range(l, c, layer + 1, index * 2);
    find_range(c+1, r, layer + 1, index * 2 | 1);
}

vector<int> restore_permutation(int n_, int W, int R)
{
    N = n_;
    add_ranges(0, N-1);
    compile_set();

    int layerCnt = __builtin_ctz(N);
    bs.resize(layerCnt + 1);

    for (int i = 0; i <= layerCnt; i++)
        bs[i].resize(1 << i);

    for (int i = 0; i < N; i++)
        bs[0][0].insert(i);

    find_range(0, N-1, 0, 0);

    vector<int> perm(N);
    for (int i = 0; i < N; i++)
    {
        int index = *bs[layerCnt][i].begin(); 
        perm[index] = i;
    }
    return perm;
}

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