Submission #66349

#	Time	Username	Problem	Language	Result	Execution time	Memory
66349		aquablitz11	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	512 KiB

messy

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

using pii = pair<int, int>;
const int N = 128;
const int LN = 7;

int n, ln, ans[N][LN]; // 1 = left, 0 = right

string construct(int l, int r, int ca)
{
    string s(n, '0');
    for (int i = 0; i < l; ++i)
        s[i] = i < ca ? '1' : '0';
    for (int i = n-1; i > r; --i)
        s[i] = '1';
    return s;
}

void build_tree(int l, int r, int ca)
{
    if (l == r) return;
    string s = construct(l, r, ca);
    int m = (l+r)/2;
    for (int i = l; i <= m; ++i) {
        string t(s);
        t[i] = '1';
        add_element(t);
    }
    build_tree(l, m, ca);
    build_tree(m+1, r, ca+1);
}

pii getrange(int i)
{
    int l = 0, r = n-1;
    for (int j = 0; j < ln; ++j) {
        if (ans[i][j] == -1) break;
        int m = (l+r)/2;
        if (ans[i][j] == 1) r = m;
        else l = m+1;
    }
    return pii(l, r);
}

void query_tree(int l, int r, int ca, int dep)
{
    if (l == r) return;
    string s = construct(l, r, ca);
    string q(n, '0');
    for (int i = 0; i < n; ++i) {
        pii ri = getrange(i);
        if (ri != pii(l, r))
            q[i] = s[ri.first];
    }
    for (int i = 0; i < n; ++i) {
        pii ri = getrange(i);
        if (ri == pii(l, r)) {
            string t(q);
            t[i] = '1';
            bool ret = check_element(t);
            ans[i][dep] = ret?1:0;
        }
    }
    int m = (l+r)/2;
    query_tree(l, m, ca, dep+1);
    query_tree(m+1, r, ca+1, dep+1);
}

vector<int> restore_permutation(int n, int w, int r)
{
    ::n = n;
    ln = 0;
    while ((1<<ln) < n) ++ln;
    for (int i = 0; i < n; ++i) for (int j = 0; j < ln; ++j)
        ans[i][j] = -1;
    build_tree(0, n-1, 0);
    compile_set();
    query_tree(0, n-1, 0, 0);

    vector<int> ans;
    for (int i = 0; i < n; ++i)
        ans.push_back(getrange(i).first);
    return ans;
}

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