Submission #48471

#	Time	Username	Problem	Language	Result	Execution time	Memory
48471		rzbt	Unscrambling a Messy Bug (IOI16_messy)	C++14	0 / 100	2 ms	384 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int n;
string ele="0";
string nele;
void dodavanje(int l,int d,string osnova){
    if(l==d)return;
    int mid=(l+d)/2;
    for(int i=l;i<=mid;i++){
        osnova[i]='1';
        add_element(osnova);
        osnova[i]='0';
    }
    string o1=ele;
    string o2=o1;
    for(int i=l;i<=mid;i++)o1[i]='1';
    for(int i=mid+1;i<=d;i++)o2[i]='1';
    dodavanje(l,mid,osnova);
    dodavanje(mid+1,d,osnova);
}
int perm[1026];
void resavanje(int l,int d,string osnova,string nadskup){
    if(d-l==1){
        for(int i=0;i<n;i++){
            if(nadskup[i]=='1'){
                osnova[i]='1';
                bool dali=check_element(osnova);
                if(dali)perm[l]=i;
                else perm[d]=i;

            }
        }
        return;
    }
    string levo=ele;
    string desno=ele;
    for(int i=0;i<n;i++){
        if(nadskup[i]=='1'){
            osnova[i]='1';
            bool dali=check_element(osnova);
            if(dali)levo[i]='1';
            else desno[i]='1';
            osnova[i]='0';
        }
    }
    int mid=(l+d)/2;
    resavanje(l,mid,desno,levo);
    resavanje(mid+1,d,levo,desno);

}
std::vector<int> restore_permutation(int _n, int w, int r) {
    n=_n;
    ele.resize(n);
    nele.resize(n);
    for(int i=0;i<n;i++)ele[i]='0';
    for(int i=0;i<n;i++)nele[i]='1';

    dodavanje(0,n,ele);
    compile_set();
    resavanje(0,1,ele,nele);
    return vector<int>(perm,perm+n);

}
/*
add_element("0");
compile_set();
check_element("0");
*/

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