Submission #141406

#	Time	Username	Problem	Language	Result	Execution time	Memory
141406		CaroLinda	Mechanical Doll (IOI18_doll)	C++14	37 / 100	494 ms	239264 KiB

doll

//Expected to be O(2N) switches
#include "doll.h"
#include <bits/stdc++.h>

#define debug printf
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int inf=1e9+10 ;
const int MAXN = 2e5+10;

using namespace std ;

int n , m , qtd ;
int triggers[MAXN*2] ;

// -------------------------

struct node
{

  int id , l , r , gate ;

} ;

node v[MAXN*4] ;

int mid(int l , int r ) { return (l+r)/2 ; }


int createTree(int pos, int l , int r , int cur )
{

  if(l==r) return cur - 1 ;


  int last = createTree( pos*2, l , mid(l,r) , cur+1 ) ;
  last = createTree(pos*2+1, mid(l,r)+1 , r , last+1 ) ;
  v[pos].id = -cur ;
  v[pos].gate = 0 ;

  //printf("%d %d has become %d\n" , l , r , cur ) ;

  return last ;

}

void simula(int pos, int l, int r , int cur )
{

  if(l==r)
  {
    v[pos].id =  triggers[cur] ;

    if( ++cur <= qtd) simula(1 , 1 , qtd  , cur ) ;

    return ;

  }

  int nxt = pos*2 ;
  pii p = mk( l , mid(l,r) ) ;

  if( v[pos].gate == 1 )
  {
    nxt ++ ;
    p = mk(mid(l,r)+1, r) ;
  }

  v[pos].gate = !v[pos].gate ;

  simula(nxt , p.ff , p.ss , cur ) ;

  v[pos].l  =v[pos*2].id ;
  v[pos].r = v[pos*2+1].id ;

}

void print(int pos, int l, int r)
{

  printf("%d %d -> %d %d\n" , l , r , v[pos].l , v[pos].r ) ;

  if(l==r) return ;

  print(pos*2, l , mid(l,r)) ;
  print(pos*2+1, mid(l,r)+1, r) ;

}

void create_circuit(int M, vector<int> A) 
{
  m = M ;
  n = A.size() ;
  lp(i,1,n+1) triggers[i] = A[i-1] ;
  ++ n ;

  for(int i = 0 ; i <= 21 ; i++ )
    if( (1<<i) >= n )
      { qtd = (1<<i) ; break ; }

  lp(i , n , qtd ) triggers[i] = -1 ;
  triggers[qtd] = 0 ;

  vector<int> c(m+1) ;

  lp(i,0,m+1) c[i] = -1 ;

  createTree( 1 , 1 , qtd , 1 ) ;
  simula(1 , 1 , qtd , 1 ) ; 

  //print(1,1,qtd) ;

  vector<int> x(qtd-1) , y(qtd-1) ;

  lp(i,1,qtd)
    {

      int curId = -v[i].id ;

      x[curId-1] = v[i].l ;
      y[curId-1] = v[i].r ;

    }

  /*printf("%d switches\n" , qtd-1) ;

  lp(i,1,qtd) printf("%d %d\n" , x[i-1] , y[i-1]); */

  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