Submission #588070

#	Time	Username	Problem	Language	Result	Execution time	Memory
588070		Deepesson	Mechanical Doll (IOI18_doll)	C++17	47 / 100	154 ms	51032 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;
void gera_ordem(int l,int r,int pos=1){
    if(l==r){
     //   std::cout<<l<<" "<<segue[count]<<"\n";
        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];
}

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(l!=m)
        con[pos].push_back(-(pos*2));
    else con[pos].push_back(indice[l]);
    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 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;
       }
    }
    while(A.size()<obj-1){
        A.push_back(-1);
    }
    A.push_back(0);
   int N = A.size();
   segue=A;
   for(int i=0;i!=N;++i){
        gera_ordem(0,N-1);
   }
   build(0,N-1);
   std::vector<int> emp;
   for(int i=0;i!=M+1;++i)emp.push_back(-1);
   emp[0]=begin;
   std::vector<int> a,b;
    for(int i=1;i<=max;++i){
       // std::cout<<con[i].size()<<"!!\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";
    }
   answer(emp,a,b);
}

Compilation message (stderr)

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