Submission #297642

#	Time	Username	Problem	Language	Result	Execution time	Memory
297642		davi_bart	Mechanical Doll (IOI18_doll)	C++14	53 / 100	151 ms	13200 KiB

doll

#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
#define ll long long
#define fi first
#define se second

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

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> C(M+1,0);
  vector<int> X,Y;

  vector<int> volte[M+2];
  vector<bool> vis(M+2,0);
  A.push_back(0);
  for(int i=0;i<A.size()-1;i++){
      volte[A[i]].push_back(A[i+1]);
  }
  C[0]=A[0];
  int S=1;
  for(int i=0;i<A.size()-1;i++){
    int x=A[i];
    if(volte[x].size()>=2){
      if(vis[x])continue;
      vis[x]=1;
      int y=volte[x].size();
      int lg=31-__builtin_clz(y);
      if((1<<lg)!=y)lg++;
    //cout<<lg<<endl;
      vector<int> k(1<<lg);
      for(int i=0;i<lg;i++){
        for(int j=0;j<(1<<lg);j+=(1<<(lg-i))){
          k[j+(1<<(lg-i-1))]=k[j]+(1<<i);
        }
      }
      C[A[i]]=-S;
      int q=volte[x].back();
      volte[x].pop_back();
      while(volte[x].size()<(1<<lg))volte[x].push_back(-S);
      volte[x].pop_back();
      volte[x].push_back(q);
      //for(int a:volte[x])cout<<a<<" ";
      //cout<<endl;
      int s=S;
      for(int i=1;i<(1<<lg);i++){
        if(i<(1<<(lg-1))){
          X.push_back(-(2*i+s-1));
          Y.push_back(-(2*i+s));
        }else{
          X.push_back(volte[x][k[2*i-(1<<lg)]]);
          Y.push_back(volte[x][k[2*i+1-(1<<lg)]]);
        }
        S++;
      }
      continue;
    }
    C[x]=A[i+1];
  }
  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i=0;i<A.size()-1;i++){
      |               ~^~~~~~~~~~~
doll.cpp:23:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i=0;i<A.size()-1;i++){
      |               ~^~~~~~~~~~~
doll.cpp:41:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |       while(volte[x].size()<(1<<lg))volte[x].push_back(-S);
      |             ~~~~~~~~~~~~~~~^~~~~~~~
doll.cpp:11:7: warning: unused variable 'N' [-Wunused-variable]
   11 |   int N = A.size();
      |       ^

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