Submission #1188739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188739		Ak_16	Mechanical Doll (IOI18_doll)	C++20	84 / 100	46 ms	25136 KiB

doll

#include <iostream>
#include <vector>
#include "doll.h"
using namespace std;

int bad[1000000];
int po[20];
int n;
int inc[1000000];
  int l[1000000];
  int r[1000000];
  int par[1000000];
  int swi[1000000];
  int swipos[1000000];
  int tri[1000000];
  int tripos[1000000];
  int lf;
  int scnt;
  int tcnt;
  vector<int> c;
  vector<int> x;
  vector<int> y;
  int nx;
  
void rem(int num){
  bad[num]=1;
  if(inc[num]==0){return;}
  
  int n1 = num + inc[num];
  int n2 = num + 2*inc[num];
  rem(n1);
  rem(n2);
}


void create_circuit(int m, vector<int> a){
  for(int i=0; i<1e6; i++){
    bad[i]=0;
  }
  
  n = a.size();
  int anew[1000000];
  for(int i=0; i<n; i++){
    anew[i]=a[i];
  }
  anew[n]=0;
  
  po[0]=1;
  
  for(int i=1; i<=19; i++){
    po[i] = 2*po[i-1];
  }
  
  
  
  
  c.push_back(a[0]);

  for(int i=1; i<=m; i++){
    c.push_back(-1);
  }
  
  
  
  for(int i=0; i<=20; i++){
    if(po[i]>=n){
      nx=i; break;
    }
  }
  
  for(int i=0; i<nx; i++){
    for(int j=po[i]; j<po[i+1]; j++){
      l[j] = j+po[i];
      r[j] = j+po[i+1];
      
      par[j+po[i]] = j;
      par[j+po[i+1]] = j;
      
      inc[j] = po[i];
    }
  }
  
  for(int i=po[nx]; i<po[nx+1]; i++){
    inc[i]=0;
  }
  
   lf=po[nx]-n;
  
  int bi[30];
  
  for(int i=19; i>=0; i--){
    if(lf>=po[i]){
      bi[i]=1;
      lf -= po[i];
    }
    else {
      bi[i]=0;
    }
  }
  
  
  for(int i=0; i<=nx; i++){
    if(bi[nx-i]==1){
      int imp;
      for(int j=po[i]; j<po[i+1]; j++){
        if(bad[j]==0){
          imp=j; break;
        }
      }
      
      rem(imp);
    }
  }
  
  scnt=0;
  tcnt=0;
  
  for(int i=po[nx]; i<po[nx+1]; i++){
    if(bad[i]==0){
      tcnt++;
      tri[tcnt]=i;
      tripos[i]=tcnt;
    }
  }
  
  for(int i=1; i<po[nx]; i++){
    if(bad[i]==0){
      scnt++;
      swi[scnt]=i;
      swipos[i]=scnt;
    }
  }
  
  
  
  for(int i=1; i<=scnt; i++){
    int k = swi[i];
    if(bad[l[k]]==1){
      x.push_back(-1);
    }
    else if(inc[l[k]]==0){
      x.push_back(anew[tripos[l[k]]]);
      
    }
    else {
      x.push_back(-swipos[l[k]]);
    }
    if(bad[r[k]]==1){
      y.push_back(-1);
    }
    else if(inc[r[k]]==0){
      y.push_back(anew[tripos[r[k]]]);
    }
    else {
      y.push_back(-swipos[r[k]]);
    }
  }
  
  answer(c, x, y);
  
}

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