Submission #535301

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

messy

#include <bits/stdc++.h>

#include "messy.h"
void divide(int la,int ra,std::string tot){
    if(la==ra){
        return;
    }
    int m = (la+ra)/2;
    ///Adiciona N/2 elementos por nivel
    for(int i=la;i<=m;++i){
        std::string x = tot;
        x[i]='1';
        add_element(x);
    }
    {
        std::string copia = tot;
        for(int i=m+1;i<=ra;++i){
            copia[i]='1';
        }
        divide(la,m,copia);
    }
    {
        std::string copia = tot;
        for(int i=la;i<=m;++i){
            copia[i]='1';
        }
        divide(m+1,ra,copia);
    }
}
int indices[300];
void gerar(int la,int ra,std::vector<int> valido,std::string lixo){
    if(la==ra){
      ///  std::cout<<valido.size()<<"\n";
        assert(valido.size()==1);
        indices[valido[0]]=la;
        return;
    }
  ///  std::cout<<valido.size()<<" "<<(ra-la+1)<<" "<<la<<" "<<ra<<"\n";
    std::vector<int> a,b;
    for(auto&x:valido){
        std::string copia = lixo;
        copia[x]='1';
        bool res = check_element(copia);
        if(res){
            a.push_back(x);
        }else b.push_back(x);
    }
 ///   std::cout<<valido.size()<<" "<<(ra-la+1)<<" "<<a.size()<<" "<<b.size()<<"\n";
    int m = (la+ra)/2;
    {
        std::string novastr=lixo;
        for(auto&x:b)novastr[x]='1';
        gerar(la,m,a,novastr);
    }
    {
        std::string novastr=lixo;
        for(auto&x:a)novastr[x]='1';
        gerar(m+1,ra,b,novastr);
    }
}
std::vector<int> restore_permutation(int n, int w, int r) {
    std::string g;
    for(int i=0;i!=n;++i)g+='0';
    std::vector<int> a;
    for(int i=0;i!=n;++i)a.push_back(i);
  ///  std::cout<<a.size()<<"!!\n";
    divide(0,n-1,g);
  ///  std::cout<<"ok\n";
    compile_set();
    gerar(0,n-1,a,g);
    std::vector<int> ans;
    for(int i=0;i!=n;++i)ans.push_back(indices[i]);

    return ans;
}

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