Submission #75449

#	Time	Username	Problem	Language	Result	Execution time	Memory
75449		C_SUNSHINE	Mechanical Doll (IOI18_doll)	C++14	37 / 100	135 ms	9724 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));
    }
  }
  if(X.size()>N*2)while(1);
  //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);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:46:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |   if(X.size()>N*2)while(1);
      |      ~~~~~~~~^~~~

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