Submission #139390

#	Time	Username	Problem	Language	Result	Execution time	Memory
139390		wmrmr	Mechanical Doll (IOI18_doll)	C++17	6 / 100	135 ms	14528 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
const int MAX = 1e5+10; 
vector<int> g[MAX], ans, ansx, ansy;
int out[MAX], x[MAX], y[MAX];
int qtdS, n;
int New()
{
  int ret = -(++qtdS);
  return ret;
}
void Build(int v,vector<int> ord)
{
  int k = - v - 1;
  int grau = ord.size();
  if( grau == 2 )
  {
    x[k] = ord[0];
    y[k] = ord[1];
    return;
  }
  vector<int> first, second;
  if(grau % 2) 
  {
  	first.push_back( v ), second.push_back(ord[0]);
  	for(int i=1;i<grau;i++)
 	 {
  	 	int prox = ord[i];
  	 	if(i%2) first.push_back(prox);
  	 	else second.push_back(prox);
  	}
  }
  else
  {
  	for(int i=0;i<grau;i++)
  	{
  		int prox = ord[i];
  		if(i%2) second.push_back(prox);
  		else first.push_back(prox);
  	}
  }
  int n1 = New(), n2 = New();
  x[k] = n1; y[k] = n2;
  Build(n1,first); Build(n2,second);
  return;
}
void SetSwitch(int v)
{
  int grau = g[v].size();
  if(grau == 0){ out[v] = 0; return; }
  if(grau == 1){ out[v] = g[v][0]; return; }
  out[v] = New() ;
  Build( out[v], g[v] );
  return;
}
void create_circuit(int M, vector<int> A)
{
  n = A.size();
  g[0].push_back(A[0]); 
  for(int i=0;i<n-1;i++)
  {
    g[A[i]].push_back(A[i+1]);
  }
  g[A[n-1]].push_back(0);
  for(int i=0;i<=M;i++)
  {
    SetSwitch( i );
  }
  for(int i=0;i<=M;i++) ans.push_back(out[i]);
  for(int i=0;i<qtdS;i++) ansx.push_back(x[i]), ansy.push_back(y[i]);
  answer(ans,ansx,ansy);
  return;
}

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