Submission #1039640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039640		NeroZein	Mechanical Doll (IOI18_doll)	C++17	53 / 100	130 ms	19496 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std; 

int idd; 
int n, m;
vector<int> a;
vector<int> x, y;

void build(const int root, int nd, int l, int r, vector<int> cur, bool left) {
  if (l == r) {
    return; 
  }
  vector<int> lx, rx;
  for (int i = 0; i < (int) cur.size(); ++i) {
    if (i % 2 == 0) {
      lx.push_back(cur[i]);        
    } else {
      rx.push_back(cur[i]); 
    }
  }
  int mid = (l + r) >> 1;
  //if (!left && rx.empty()) {
    //swap(lx, rx);
  //}
  //cerr << "lx: ";
  //for (int i : lx) {
    //cerr << i << ' ';
  //}
  //cerr << '\n';
  //cerr << "rx: ";
  //for (int i : rx) {
    //cerr << i << ' ';
  //}
  //cerr << '\n';
  assert(!lx.empty() && !rx.empty());
  if (l < mid) {
    x[-nd - 1] = --idd;
    x.push_back(0);
    y.push_back(0); 
    build(root, idd, l, mid, lx, true); 
  } else {
    if (lx[0] == -1) {
      x[-nd - 1] = root; 
    } else {
      x[-nd - 1] = a[lx[0] + 1]; 
    }
  }
  if (mid + 1 < r) {
    y[-nd - 1] = --idd; 
    x.push_back(0);
    y.push_back(0);
    build(root, idd, mid + 1, r, rx, left); 
  } else {
    if (rx[0] == -1) {
      y[-nd - 1] = root; 
    } else {
      y[-nd - 1] = a[rx[0] + 1]; 
    }
  }
}

void create_circuit(int m_, vector<int> a_) {
  m = m_; 
  a = a_;
  n = (int) a.size();
  a.insert(a.begin(), 0); 
  a.push_back(0); 
  vector<vector<int>> occ(m + 1);
  for (int i = 0; i < n + 1; ++i) {
    occ[a[i]].push_back(i); 
  }
  idd = 0; 
  vector<int> c;
  c.resize(m + 1); 
  for (int i = 0; i <= m; ++i) {
    int sz = occ[i].size();
    if (!sz) {
      continue; 
    }
    if (sz == 1) {
      c[i] = a[occ[i][0] + 1];
      continue; 
    }
    int lg = 32 - __builtin_clz(sz);
    if ((sz & (sz - 1)) == 0) {//power of two 
      lg--; 
    }
    int leaves = 1 << lg; 
    vector<int> o;
    for (int j = 0; j < leaves - sz; ++j) {
      o.push_back(-1); 
    }
    for (int j : occ[i]) {
      o.push_back(j); 
    }
    c[i] = --idd;
    x.push_back(0);
    y.push_back(0);
    build(idd, idd, 1, leaves, o, 0); 
  }
  //cerr << "occ[1]: ";
  //for (int j : occ[1]) {
    //cerr << j << ' ';
  //}
  //cerr << '\n';
  //cerr << "C: "; 
  //for (int i = 0; i <= m; ++i) {
    //cerr << c[i] << " \n"[i == m];
  //}
  //cerr << "X: ";
  //for (int i = 0; i < -idd; ++i) {
    //cerr << x[i] << " \n"[i == -idd - 1];
  //}
  //cerr << "Y: ";
  //for (int i = 0; i < -idd; ++i) {
    //cerr << y[i] << " \n"[i == -idd - 1];
  //}
  answer(c, x, y);
}

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