Submission #588099

#	Time	Username	Problem	Language	Result	Execution time	Memory
588099		Deepesson	Mechanical Doll (IOI18_doll)	C++17	47 / 100	152 ms	52100 KiB

doll

#include <bits/stdc++.h>
#define MAX 305000

void create_circuit(int M, std::vector<int> A);

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

bool tab[MAX*4];
std::vector<int> segue;
std::vector<int> con[MAX*4];
int indice[MAX];
int count=0;
int max=0;
int skip=0;
void gera_ordem(int l,int r,int pos=1){
    if(l==r){
        if(l<skip){indice[l]=-1;return;}
        indice[l]=segue[count];
        ++count;
        return;
    }
    int m = (l+r)/2;

    if(!tab[pos]){
        gera_ordem(l,m,pos*2);
    }else gera_ordem(m+1,r,(pos*2)+1);
    tab[pos]=!tab[pos];
}
int validos[MAX*4];
void build(int l,int r,int pos=1){
    if(l==r)return;
    int m =(l+r)/2;
    max=std::max(max,pos);
  //  std::cout<<pos<<" "<<l<<" "<<r<<" "<<m<<"\n";
    if(!validos[pos*2]){
        con[pos].push_back(-1);
    }else if(l!=m)
        con[pos].push_back(-(pos*2));
    else con[pos].push_back(indice[l]);

    if(!validos[(pos*2)+1]){
        con[pos].push_back(-1);
    }else if(r!=m+1)
        con[pos].push_back(-((pos*2)+1));
    else con[pos].push_back(indice[r]);

  //  std::cout<<indice[l]<<" "<<indice[r]<<"\n";
   // std::cout<<"Forja "<< con[pos][0]<<" "<<con[pos][1]<<"\n";
    build(l,m,pos*2);
    build(m+1,r,(pos*2)+1);
}
void prepare_ground(int l,int r,int pos=1){
    if(l==r){
        if(indice[l]!=-1){
            ++validos[pos];
        }
        return;
    }
    int m =(l+r)/2;
    prepare_ground(l,m,pos*2);
    prepare_ground(m+1,r,(pos*2)+1);
    validos[pos]=validos[pos*2]+validos[(pos*2)+1];
}

void create_circuit(int M, std::vector<int> A) {
    if(A.size()==1){
        std::vector<int> a,b,c;
        a.push_back(A[0]);
        for(int i=1;i!=M+1;++i){
            a.push_back(0);
        }
        answer(a,b,c);
        return;
    }
    int begin = A[0];
    {
        std::vector<int> novA;
        for(int i=1;i!=A.size();++i)novA.push_back(A[i]);
        A=novA;
    }
    int obj=0;
    for(int i=1;;i*=2){
       if(i>A.size()){
          obj=i;break;
       }
    }
    segue=A;
    segue.push_back(0);
 //   obj=A.size()+(A.size()&1);
    while(A.size()<obj-1){
        A.push_back(-1);
        ++skip;
    }
    A.push_back(0);
   int N = A.size();

   for(int i=0;i!=N;++i){
        gera_ordem(0,N-1);
   }
 //  printf("ok\n");
 prepare_ground(0,N-1);
   build(0,N-1);
   for(int i=1;i<=max;++i){
  //  std::cout<<tab[i]<<" "<<i<<" estado!\n";
   }
   std::vector<int> emp;
   for(int i=0;i!=M+1;++i)emp.push_back(-1);
   emp[0]=begin;
   std::vector<int> a,b;
  // printf("bora\n");
    for(int i=1;i<=max;++i){
        while(con[i].size()<2){
            con[i].push_back(-1);
        }
       // std::cout<<con[i].size()<<" "<<i<<"!!\n";
        a.push_back(con[i][0]);
        b.push_back(con[i][1]);
      //  std::cout<<i<<" "<<con[i][0]<<"\n";
      //  std::cout<<i<<" "<<con[i][1]<<"\n";
    }
  //  printf("resolvido\n");
   answer(emp,a,b);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int i=1;i!=A.size();++i)novA.push_back(A[i]);
      |                     ~^~~~~~~~~~
doll.cpp:83:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |        if(i>A.size()){
      |           ~^~~~~~~~~
doll.cpp:90:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |     while(A.size()<obj-1){
      |           ~~~~~~~~^~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56