Submission #1199680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199680		qs1	Mechanical Doll (IOI18_doll)	C++20	53 / 100	61 ms	14124 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define lli int


lli invert(lli i,lli n){//indexed in 0
  lli r=0;
  while(n>1){
    r*=2;
    r+=i%2;
    n/=2;
    i/=2;
  }
  return r;
}


void create_circuit(int y, vector<int> l) {
  y++;
  int x = l.size();
  lli ai=-1,s,n,lst;
  l.push_back(0);
  vector<lli> vx, vy,r(y);
  vector<vector<lli>>va(y);
  for(lli i=0;i<x;i++){
    va[l[i]].push_back(l[i+1]);
  }
  r[0]=l[0];
  for(lli i=1;i<y;i++){
    if(va[i].size()==0)r[i]=0;
    else if(va[i].size()==1)r[i]=va[i][0];
    else if(va[i].size()==2){
      r[i]=ai;
      ai--;
      vx.push_back(va[i][0]);
      vy.push_back(va[i][1]);
    }
    else{
      lli n=1;
      r[i]=ai;
      vx.push_back(ai-1);
      vy.push_back(ai-2);
      ai--;
      while(n*2<va[i].size()){
        if(n!=1){
          for(lli i=0;i<n;i++){
            vx.push_back(ai-2*i-n);
            vy.push_back(ai-2*i-n-1);
          }
          ai-=n;
        }
        n*=2;
      }
      lst=va[i][va[i].size()-1];
      for(lli ii=0;ii<2*n-1;ii++){
        s=invert(ii,n*2);
        if(ii%2){
          if(s>=va[i].size()-1)vy.push_back(ai+n-1);
          else vy.push_back(va[i][s]);
        }
        else{
          if(s>=va[i].size()-1)vx.push_back(ai+n-1);
          else vx.push_back(va[i][s]);
        }
      }
      vy.push_back(lst);
      ai-=n;
    }
  }
  answer(r, vx, vy);
}

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