oj.uz

Submission #588106

# Submission time Handle Problem Language Result Execution time Memory
588106 2022-07-02T17:30:09 Z Deepesson Mechanical Doll (IOI18_doll) C++17
100 / 100
 156 ms 53912 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29012 KB Output is correct
2 Correct 63 ms 36484 KB Output is correct
3 Correct 79 ms 39108 KB Output is correct
4 Correct 14 ms 28884 KB Output is correct
5 Correct 23 ms 30176 KB Output is correct
6 Correct 80 ms 42360 KB Output is correct
7 Correct 13 ms 28884 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29012 KB Output is correct
2 Correct 63 ms 36484 KB Output is correct
3 Correct 79 ms 39108 KB Output is correct
4 Correct 14 ms 28884 KB Output is correct
5 Correct 23 ms 30176 KB Output is correct
6 Correct 80 ms 42360 KB Output is correct
7 Correct 13 ms 28884 KB Output is correct
8 Correct 88 ms 43716 KB Output is correct
9 Correct 118 ms 48408 KB Output is correct
10 Correct 142 ms 53912 KB Output is correct
11 Correct 14 ms 28884 KB Output is correct
12 Correct 14 ms 28884 KB Output is correct
13 Correct 17 ms 28884 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29012 KB Output is correct
2 Correct 63 ms 36484 KB Output is correct
3 Correct 79 ms 39108 KB Output is correct
4 Correct 14 ms 28884 KB Output is correct
5 Correct 23 ms 30176 KB Output is correct
6 Correct 80 ms 42360 KB Output is correct
7 Correct 13 ms 28884 KB Output is correct
8 Correct 88 ms 43716 KB Output is correct
9 Correct 118 ms 48408 KB Output is correct
10 Correct 142 ms 53912 KB Output is correct
11 Correct 14 ms 28884 KB Output is correct
12 Correct 14 ms 28884 KB Output is correct
13 Correct 17 ms 28884 KB Output is correct
14 Correct 143 ms 53804 KB Output is correct
15 Correct 112 ms 49972 KB Output is correct
16 Correct 136 ms 53704 KB Output is correct
17 Correct 13 ms 28884 KB Output is correct
18 Correct 13 ms 28944 KB Output is correct
19 Correct 13 ms 28884 KB Output is correct
20 Correct 133 ms 53780 KB Output is correct
21 Correct 13 ms 29004 KB Output is correct
22 Correct 13 ms 28884 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28960 KB Output is correct
2 Correct 13 ms 28960 KB Output is correct
3 Correct 15 ms 28992 KB Output is correct
4 Correct 14 ms 28884 KB Output is correct
5 Correct 16 ms 28884 KB Output is correct
6 Correct 15 ms 28884 KB Output is correct
7 Correct 16 ms 28884 KB Output is correct
8 Correct 14 ms 28888 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28884 KB Output is correct
2 Correct 76 ms 41964 KB Output is correct
3 Correct 112 ms 46732 KB Output is correct
4 Correct 129 ms 51104 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28884 KB Output is correct
2 Correct 76 ms 41964 KB Output is correct
3 Correct 112 ms 46732 KB Output is correct
4 Correct 129 ms 51104 KB Output is correct
5 Correct 133 ms 52700 KB Output is correct
6 Correct 156 ms 52152 KB Output is correct
7 Correct 136 ms 52124 KB Output is correct
8 Correct 130 ms 52200 KB Output is correct
9 Correct 115 ms 48252 KB Output is correct
10 Correct 131 ms 51804 KB Output is correct
11 Correct 135 ms 51496 KB Output is correct
12 Correct 112 ms 46688 KB Output is correct
13 Correct 99 ms 42300 KB Output is correct
14 Correct 110 ms 47060 KB Output is correct
15 Correct 114 ms 47080 KB Output is correct
16 Correct 16 ms 29524 KB Output is correct
17 Correct 75 ms 41672 KB Output is correct
18 Correct 76 ms 42120 KB Output is correct
19 Correct 111 ms 46700 KB Output is correct
20 Correct 128 ms 52056 KB Output is correct
21 Correct 131 ms 51420 KB Output is correct
22 Correct 155 ms 51472 KB Output is correct