Submission #300275

#	Time	Username	Problem	Language	Result	Execution time	Memory
300275		MickyOr	Mechanical Doll (IOI18_doll)	C++17	100 / 100	690 ms	60636 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define fore(i, b, e) for (int i = b; i < (int)e; ++i)
#define pb push_back

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;

vector<vi> G;
vi leafs;
map<int, int> leafNo;

void genGraph(int lvl, int maxLvl) {
  if (lvl == maxLvl) return;
  G.pb(vi());
  int v = G.size()-1;
  if (lvl+1 != maxLvl) {
    // X
    G[v].pb(G.size());
    genGraph(lvl+1, maxLvl);
    // Y
    G[v].pb(G.size());
    genGraph(lvl+1, maxLvl);    
  }
  else {
    leafs.pb(v);
  }
}

vi order;

void genOrder(vi &vals) {
  if (vals.size() == 1) {
    order.pb(vals.back());
    return;
  }
  vi L, R;
  fore(i, 0, vals.size()) {
    if (i&1) R.pb( vals[i] );
    else L.pb( vals[i] );
  }
  genOrder(L);
  genOrder(R);
}

vector<bool> isActive;

void delSwitches(int v) {
  if (G[v].size() == 0) {
    return;
  }
  delSwitches(G[v][0]);
  delSwitches(G[v][1]);
  if (isActive[G[v][0]] || isActive[G[v][1]]) isActive[v] = true;
  else isActive[v] = false;
}

map<int, ii> switchDirs;

void genAnswer(int v, int curS, int &S) {
  if (!isActive[v] || G[v].size() == 0) return;
  int L = G[v][0];
  int R = G[v][1];
  int xS = -1, yS = -1;
  if (!isActive[L]) {
    xS = -1;
  }
  else {
    if (leafNo.count(L)) xS = leafNo[L];
    else xS = --S;
  }
  if (leafNo.count(R)) yS = leafNo[R];
  else yS = --S;
  switchDirs[curS] = {xS, yS};
  genAnswer(L, xS, S);
  genAnswer(R, yS, S);
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> C;
  std::vector<int> X, Y;
  if (N == 1) {
    C.pb(A[0]);
    fore(i, 0, M) C.pb(0);
    answer(C, X, Y);
    return;
  }
  A.pb(0);
  N++;
  int pot = 0, base = 1;
  while (base < N) {
    base <<= 1;
    pot++;
  }
  
  genGraph(0, pot+1); // las hojas son los cuadrados
  
  vi vals;
  fore(i, 0, base) vals.pb(i);
  genOrder(vals);
  vi nxt(base, -1), invP(base);
  fore(i, 0, base) {
    invP[order[i]] = i;
    leafNo[leafs[i]] = order[i];
  }
  for (int i = base-2; i >= 0; i--) {
    nxt[i] = invP[i+1];
  }

  isActive.assign(G.size(), false);
  for (int i = base-1, j = 0; j < N; j++, i--) {
    isActive[leafs[i]] = true;
  }

  delSwitches(0);
  int accDel = 0;
  fore(i, 0, base) {
    int leaf = leafs[invP[i]];
    if (!isActive[leaf]) accDel++;
    else leafNo[leaf] = A[ leafNo[leaf] - accDel ];
  }

  fore(i, 0, M+1) C.pb(-1);
  int S = -1;
  genAnswer(0, -1, S);
  for (int i = -1; i >= S; --i) {
    assert( switchDirs.count(i) == 1 );
    X.pb(switchDirs[i].first);
    Y.pb(switchDirs[i].second);
  }

  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