Submission #1244946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244946		lncreedible	Mechanical Doll (IOI18_doll)	C++20	84 / 100	97 ms	11016 KiB

doll

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

#define mkp make_pair
#define eb emplace_back

using ii = pair<int, int>;
using iii = pair<ii, int>;

int swid = -1;
vector<int> sx, sy;

vector<iii> go(int h, int rem) {
  vector<iii> ret;
  int me = ++swid;
  if (h == 1) {
    ret.eb(mkp(me, 1), 2);
    if (rem != 1) ret.eb(mkp(me, 0), 1);
    return ret;
  }
  sy[me] = -swid - 2;
  vector<iii> left, right = go(h - 1, rem);
  if (rem > (1 << (h - 1))) {
    sx[me] = -swid - 2;
    left = go(h - 1, rem - (1 << (h - 1)));
  }
  for (auto &p : left) ret.eb(mkp(p.first.first, p.first.second), p.second * 2 - 1);
  for (auto &p : right) ret.eb(mkp(p.first.first, p.first.second), p.second * 2);
  return ret;
}

bool cmp(const iii &a, const iii &b) {
  return a.second < b.second;
}

void create_circuit(int m, vector<int> seq) {
  seq.eb(0);
  int sz = seq.size();
  vector<int> conn(m + 1, -1);
  sx.assign(2 * sz, -1);
  sy.assign(2 * sz, -1);
  vector<iii> order = go(32 - __builtin_clz(sz), sz);
  sort(order.begin(), order.end(), cmp);
  for (int i = 0; i < sz; ++i) {
    if (order[i].first.second) sy[order[i].first.first] = seq[i];
    else sx[order[i].first.first] = seq[i];
  }
  while (!sx.empty() && sx.back() == -1 && sy.back() == -1) {
    sx.pop_back(); sy.pop_back();
  }
  answer(conn, sx, sy);
}

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