Submission #1216314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216314		not_amir	Mechanical Doll (IOI18_doll)	C++20	85.55 / 100	109 ms	19840 KiB

doll

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

int t = 0;
vector<int> X, Y, C;

int create_2pow(int c, int i, int tl, int tr, int &diff, vector<pair<int, int>> &vec, int self = INT_MIN) {
  if (tr - tl <= diff) {
    diff -= tr - tl;
    return self;
  }
  if (tr - tl == 2) {
    int ret = ++t;
    vec.push_back({c, ret});
    vec.push_back({c + (1 << i), -ret});
    return -ret;
  }
  int ret = ++t;
  if (self == INT_MIN)
    self = -ret;
  int tm = (tl + tr) / 2;
  X[ret - 1] = create_2pow(c, i + 1, tl, tm, diff, vec, self), Y[ret - 1] = create_2pow(c + (1 << i), i + 1,tm, tr, diff, vec, self);
  return -ret;
}

int create(vector<int> &leaf) {
  if (leaf.size() == 1)
    return leaf[0];
  int n = 1 << 32 - __builtin_clz(leaf.size() - 1);
  int diff = n - leaf.size();
  vector<pair<int, int>> vec;
  int ret = create_2pow(0, 0, 0, n, diff, vec);
  sort(vec.begin(), vec.end());
  if (diff) {
    leaf.push_back(ret);
    swap(leaf[leaf.size() - 1], leaf[leaf.size() - 2]);
  }
  for (int i = 0; i < vec.size(); i++) {
    int ret = vec[i].second;
    if (ret > 0)
      X[ret - 1] = leaf[i];
    else
      Y[-ret - 1] = leaf[i];
  }
  return ret;
}

void create_circuit(int M, vector<int> A) {
  int N = A.size();
  A.push_back(0);
  C.resize(M + 1, 0);
  C[0] = A[0];
  map<int, vector<int>> mp;
  for (int i = 1; i <= N; i++)
    mp[A[i - 1]].push_back(A[i]);
  X.resize(2 * N), Y.resize(2 * N);
  for (auto [v, leaf] : mp)
    C[v] = create(leaf);
  X.resize(t), Y.resize(t);
  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: 41.553 / 56