oj.uz

Submission #141522

# Submission time Handle Problem Language Result Execution time Memory
141522 2019-08-08T09:57:18 Z CaroLinda Mechanical Doll (IOI18_doll) C++14
100 / 100
 210 ms 24168 KB 
#include "doll.h"
#include <bits/stdc++.h>

#define printPii(p) printf("%d %d\n" ,p.ff , p.ss)
#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] ;
vector<pii> folha ;

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

struct node
{

  int id , l , r , gate ;
  bool exist ;

} ;

node v[MAXN*4] ;

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


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

  v[pos].id = -pos ;

  if(l==r) return ;


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

  v[pos].gate = 0 ;
  v[pos].exist = false ;

}

void simulate( int pos , int l , int r , int cnt )
{

  if( l == r )
  {

    folha.pb(mk( pos , cnt )) ;

    if( ++cnt <= qtd )  simulate(1 , 1 , qtd , cnt) ;

    return ;

  }

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

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

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

  simulate( idx , p.ff , p.ss , cnt ) ;

}

pii helpful[MAXN*4] ;

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

  if( l ==  r) return ;

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

  if( !v[pos*2].exist && !v[pos*2+1].exist )
  {
    v[pos].exist = false ;
    return ;
  }

  v[pos].exist = true ;
}

int cnt = 1 ;

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

  if(l==r) return ;

  if( v[pos].exist ) v[pos].id = - cnt ;
  else { v[pos].id = -1 ; return ; }

  cnt ++ ;

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

  v[pos].l = ( v[pos*2].exist ? v[pos*2].id : -1 ) ;
  v[pos].r = ( v[pos*2+1].exist ? v[pos*2+1].id : -1 ) ;

  int idx = -v[pos].id ;

  helpful[idx] = mk( v[pos].l , v[pos].r ) ;

}

void print(int pos,  int l , int r )
{
  printf("%d (%d %d) -> %d %d %d\n" , pos , l , r , v[pos].id , v[pos].l , v[pos].r ) ;
  printf("%d!\n" , v[pos].exist ) ;
  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] ;
  triggers[++n] = 0 ;

  vector<int> c(m+1) ;
  lp(i,0,m+1) c[i] = -1 ;



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


  createTree( 1 , 1 , qtd );
  simulate(1,1,qtd , 1) ;

  sort( folha.begin() , folha.end() ) ;    //ordena por id na arvore
  reverse(folha.begin() , folha.end() ) ;
  lp(i,0,n) swap( folha[i].ff  ,folha[i].ss ) ;
  sort( folha.begin() , folha.begin() + n ) ; //ordena os n ultimos por oderm de processamento
  lp(i,0,n) 
  {
    int idx = folha[i].ss ;

    v[ idx ].id = triggers[i+1] ;
    v[idx].exist = true ;
  }

  finalize(1,1,qtd) ;
  lastProcessing(1,1,qtd) ;
 // print(1,1,qtd);

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

  lp(i,0,cnt-1) 
  {
    x[i] = helpful[i+1].ff ;
    y[i] = helpful[i+1].ss ;
  }

  answer(c,x,y) ;

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 71 ms 10936 KB Output is correct
3 Correct 69 ms 10520 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 86 ms 12744 KB Output is correct
7 Correct 1 ms 256 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 71 ms 10936 KB Output is correct
3 Correct 69 ms 10520 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 86 ms 12744 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 150 ms 20100 KB Output is correct
9 Correct 184 ms 20628 KB Output is correct
10 Correct 187 ms 24168 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 71 ms 10936 KB Output is correct
3 Correct 69 ms 10520 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 86 ms 12744 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 150 ms 20100 KB Output is correct
9 Correct 184 ms 20628 KB Output is correct
10 Correct 187 ms 24168 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 207 ms 23816 KB Output is correct
15 Correct 155 ms 19752 KB Output is correct
16 Correct 206 ms 23644 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 178 ms 23996 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 165 ms 18900 KB Output is correct
3 Correct 135 ms 18912 KB Output is correct
4 Correct 198 ms 22360 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 165 ms 18900 KB Output is correct
3 Correct 135 ms 18912 KB Output is correct
4 Correct 198 ms 22360 KB Output is correct
5 Correct 187 ms 23528 KB Output is correct
6 Correct 207 ms 23308 KB Output is correct
7 Correct 210 ms 23492 KB Output is correct
8 Correct 192 ms 23056 KB Output is correct
9 Correct 147 ms 19040 KB Output is correct
10 Correct 184 ms 22996 KB Output is correct
11 Correct 157 ms 22680 KB Output is correct
12 Correct 163 ms 19200 KB Output is correct
13 Correct 163 ms 19496 KB Output is correct
14 Correct 147 ms 19676 KB Output is correct
15 Correct 184 ms 19748 KB Output is correct
16 Correct 4 ms 844 KB Output is correct
17 Correct 94 ms 13072 KB Output is correct
18 Correct 162 ms 19160 KB Output is correct
19 Correct 127 ms 19108 KB Output is correct
20 Correct 199 ms 22812 KB Output is correct
21 Correct 173 ms 22596 KB Output is correct
22 Correct 177 ms 22712 KB Output is correct