Submission #441152

#	Time	Username	Problem	Language	Result	Execution time	Memory
441152		prvocislo	Mechanical Doll (IOI18_doll)	C++17	100 / 100	424 ms	36080 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int maxvr = 6e5 + 100;
//const int maxvr = 100;
vector<int> num(maxvr); // naozajstne cisla vrcholov v strome. Teda switche budu zaporne a prvych m cisel budu v skutocnosti nieco ine
vector<vector<int> > g(maxvr);
int n, m, s, lf, root, first; // mame fiktivny n+1-vy trigger na to aby sme sa vratili do 0
int dfs(int l, int r)
{
  if (r < first) return root;
  if (l == r) return lf++;
  int now = s;
  s++;
  g[now].push_back(dfs(l, (l+r)/2));
  g[now].push_back(dfs((l+r)/2+1, r));
  return now;
}
vector<int> stav(maxvr, 0);
int get_next() // ideme na nasledujuci vrchol ktory ma cislo mensie ako n
{
  int vr = root;
  while (vr >= n)
  {
    int nw = g[vr][stav[vr]];
    stav[vr] ^= 1;
    vr = nw;
  }
  return vr;
}
void create_circuit(int M, vector<int> a) {
  m = M;
  a.push_back(0), n = a.size();
  lf = 0, s = n;
  int n2 = 1;
  while (n2 < n) n2 <<= 1;
  root = n, first = n2 - n; dfs(0, n2 - 1);
  for (int i = 0; i < n; i++)
  {
    int vr = get_next();
    num[vr] = a[i];
  }
  for (int i = n; i < s; i++)
  {
    num[i] = -(i - (n-1));
  }
  vector<int> c(m+1, num[root]), x(s-n), y(s-n);
  for (int i = n; i < s; i++)
  {
    x[i-n] = num[g[i][0]];
    y[i-n] = num[g[i][1]];
  }
  /*for (int i = 0; i <= m; i++) cout << i << " " << c[i] << endl;
  for (int i = 0; i < x.size(); i++)
  {
    cout << -(i+1) << " " << x[i] << endl;
    cout << -(i+1) << " " << y[i] << endl;
  }*/
  answer(c, 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