Submission #75460

#	Time	Username	Problem	Language	Result	Execution time	Memory
75460		C_SUNSHINE	Mechanical Doll (IOI18_doll)	C++14	100 / 100	125 ms	14828 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,L,R;

vector<int> rem;

vector<int> idx;

int dfn[400005],cur[400005],S=0;

int bitreverse(int x)
{
  int t=0;
  for(int i=0;i<H;i++)
    t=(t<<1)|(x&1),x>>=1;
  return t;
}

int Get(int p)
{
  if(p==(1<<H)-1)return 0;
  if(p>=(1<<H)-1-N)
  {
    idx.push_back(bitreverse(p)+1);
    return bitreverse(p)+1;
  }
  return -1;
}

void dfs(int x)
{
  if(L[-x]<-1)dfs(L[-x]);
  if(R[-x]<-1)dfs(R[-x]);
  if(L[-x]==-1&&R[-x]==-1)rem[-x]=1;
  if(L[-x]<-1&&rem[-L[-x]]&&R[-x]<-1&&rem[-R[-x]])rem[-x]=1;
}

void label(int x)
{
  dfn[-x]=++S;
  if(L[-x]<-1&&!rem[-L[-x]])label(L[-x]);
  if(R[-x]<-1&&!rem[-R[-x]])label(R[-x]);
}

void calc(int x)
{
  if(L[-x]<-1&&!rem[-L[-x]])
  {
    X[dfn[-x]-1]=-dfn[-L[-x]];
    calc(L[-x]);
  }
  else if(L[-x]>=0)
    X[dfn[-x]-1]=cur[L[-x]];
  else
    X[dfn[-x]-1]=-1;
  if(R[-x]<-1&&!rem[-R[-x]])
  {
    Y[dfn[-x]-1]=-dfn[-R[-x]];
    calc(R[-x]);
  }
  else if(R[-x]>=0)
    Y[dfn[-x]-1]=cur[R[-x]];
  else
    Y[dfn[-x]-1]=-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++);
  L.assign((1<<H),0);
  R.assign((1<<H),0);
  for(int i=1;i<(1<<H);i++)
  {
    if(i*2<(1<<H))
    {
      L[i]=-(i*2);
      R[i]=-(i*2+1);
    }
    else
    {
      L[i]=Get(i*2-(1<<H));
      R[i]=Get(i*2+1-(1<<H));
    }
  }
  
  rem.assign((1<<H),0);
  dfs(-1);
  label(-1);
  //for(int i=1;i<(1<<H);i++)cout<<dfn[i]<<' ';cout<<endl;
  sort(idx.begin(),idx.end());
  for(int i=0;i<idx.size();i++)
    cur[idx[i]]=A[i];
  X.assign(S,0);
  Y.assign(S,0);
  calc(-1);
  
  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:103:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int i=0;i<idx.size();i++)
      |               ~^~~~~~~~~~~
doll.cpp:109:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |   if(X.size()>N*2)while(1);
      |      ~~~~~~~~^~~~

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