Submission #713090

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

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
vector <int> res;
string S;
void build(int lx, int rx)
{
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    for (int i=lx; i<=mid; i++)
    {
        S[i]='1';
        add_element(S);
        S[i]='0';
    }
    for (int i=lx; i<=mid; i++) S[i]='1';
    build(mid+1,rx);
    for (int i=lx; i<=mid; i++) S[i]='0';
    for (int i=mid+1; i<=rx; i++) S[i]='1';
    build(lx,mid);
    for (int i=mid+1; i<=rx; i++) S[i]='0';
}
void dnc(int lx, int rx, vector <int> tmp)
{
    if (lx==rx)
    {
        res[tmp[0]] = lx;
        return;
    }
    int mid=(lx+rx)/2;
    vector <int> ll,rr;
    for (int i=lx; i<=rx; i++)
    {
        S[tmp[i-lx]]='1';
        bool dau = check_element(S);
        if (dau) ll.push_back(tmp[i-lx]);
        else rr.push_back(tmp[i-lx]);
        S[tmp[i-lx]]='0';
    }
    for (int i:ll) S[i]='1';
    dnc(mid+1,rx,rr);
    for (int i:ll) S[i]='0';
    for (int i:rr) S[i]='1';
    dnc(lx,mid,ll);
    for (int i:rr) S[i]='0';
}
vector<int32_t> restore_permutation(int32_t n, int32_t w, int32_t r) {
    S="";
    for (int i=0; i<n; i++) S+='0';
    build(0,n-1);
    compile_set();
    res.assign(n,0);
    vector <int> tmp;
    for (int i=0; i<n; i++) tmp.push_back(i);
    for (int i=0; i<n; i++) S[i] = '0';
    dnc(0,n-1,tmp);
    return res;
}

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