Submission #75443

#	Time	Username	Problem	Language	Result	Execution time	Memory
75443		C_SUNSHINE	Mechanical Doll (IOI18_doll)	C++14	37 / 100	105 ms	9688 KiB

doll

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include "doll.h"
using namespace std;

int N,M,H;
vector<int> C,X,Y,A;

int Get(int p)
{
  int t=p;
  p=0;
  for(int i=0;i<H;i++)
    p=(p<<1)|(t&1),t>>=1;
  if(p<N)return A[p];
  else if(p==(1<<H)-1)return 0;
  return -1;
}

void create_circuit(int M, std::vector<int> A)
{
  N=A.size();
  ::M=M;
  ::A=A;
  C.assign(M+1,-1);
  for(H=0;(1<<H)<=N;H++);
  X.resize((1<<H)-1);
  Y.resize((1<<H)-1);
  for(int i=1;i<(1<<H);i++)
  {
    if(i*2<(1<<H))
    {
      X[i-1]=-(i*2);
      Y[i-1]=-(i*2+1);
    }
    else
    {
      X[i-1]=Get(i*2-(1<<H));
      Y[i-1]=Get(i*2+1-(1<<H));
    }
  }
  //for(int i=0;i<C.size();i++)cout<<C[i]<<' ';cout<<endl;
  //for(int i=0;i<X.size();i++)cout<<X[i]<<' '<<Y[i]<<endl;
  answer(C, X, Y);
}

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