Submission #588106

#	Time	Username	Problem	Language	Result	Execution time	Memory
588106		Deepesson	Mechanical Doll (IOI18_doll)	C++17	100 / 100	156 ms	53912 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];
int gerando[MAX*4];
int valcurg[MAX*4];
int curg=1;
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(-(gerando[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(-(gerando[(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 prepare_ground2(int l,int r,int pos=1){
    if(l==r){
        return;
    }
    if(validos[pos]){
        gerando[pos]=curg;
        valcurg[curg]=pos;
        ++curg;
    }
    int m =(l+r)/2;
    prepare_ground2(l,m,pos*2);
    prepare_ground2(m+1,r,(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);
 prepare_ground2(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<curg;++i){
       // std::cout<<"Explora "<<i<<" "<<valcurg[i]<<"\n";
        while(con[valcurg[i]].size()<2){
            con[valcurg[i]].push_back(-1);
        }
       // std::cout<<con[i].size()<<" "<<i<<"!!\n";
        a.push_back(con[valcurg[i]][0]);
        b.push_back(con[valcurg[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:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int i=1;i!=A.size();++i)novA.push_back(A[i]);
      |                     ~^~~~~~~~~~
doll.cpp:99:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |        if(i>A.size()){
      |           ~^~~~~~~~~
doll.cpp:106:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     while(A.size()<obj-1){
      |           ~~~~~~~~^~~~~~

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