Submission #789941

#	Time	Username	Problem	Language	Result	Execution time	Memory
789941		Trisanu_Das	Mechanical Doll (IOI18_doll)	C++17	100 / 100	112 ms	13232 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
 
vector<int> s, x(300005), y(300005), vis(300005);
int v, b = 1, n;
 
int dfs(int l, int r){
  if(l >= n) return -1;
  if(r - l > 1){
    int mid = (l + r) / 2, u = v++;
    y[u] = dfs(l, mid);
    x[u] = dfs(mid, r);
    return -(u + 1);
  }
  return 1;
}
 
void create_circuit(int m, vector<int> a){
  s.assign(m + 1, -1);
  a.push_back(0);
  n = a.size();
  while(b < n) b *= 2;
  dfs(0, b);
  for(int i : a){
    int u = 0;
    while(u > -1){
      vis[u] ^= 1;
      int &w = vis[u] ? x[u] : y[u];
      if(w >= 0) w = i, u = -1;
      else u = -(w + 1);
    }
  }
  x.resize(v);
  y.resize(v);
  answer(s, x, y);
}

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