Submission #134310

#	Time	Username	Problem	Language	Result	Execution time	Memory
134310		WLZ	Mechanical Doll (IOI18_doll)	C++14	47 / 100	195 ms	40432 KiB

doll

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

struct node {
  node *left, *right;
  int num, level, idx;
};

int N, k = 1;
vector< pair<int, int> > tmpx, tmpy;

node* build(int num, int level, int idx, const vector<int>& A) {
  if ((1 << level) == k) {
    return new node{nullptr, nullptr, (idx == k - 1 ? 0 : (idx < N - 1 ? A[idx + 1] : -1)), level, idx};
  }
  node* left = build(num * 2, level + 1, idx, A);
  node* right = build(num * 2 - 1, level + 1, idx + (1 << level), A);
  return new node{left, right, num, level, idx};
}

void output(node* cur) {
  if ((1 << cur->level) == k) {
    return;
  }
  tmpx.push_back({cur->num, cur->left->num});
  tmpy.push_back({cur->num, cur->right->num});
  output(cur->left);
  output(cur->right);
}

void create_circuit(int M, vector<int> A) {
  N = (int) A.size();
  while (k < N) {
    k *= 2;
  }
  node* root = build(-1, 0, 0, A);
  vector<int> C(M + 1, -1);
  C[0] = A[0];
  output(root);
  sort(tmpx.rbegin(), tmpx.rend());
  sort(tmpy.rbegin(), tmpy.rend());
  vector<int> X, Y;
  for (auto& p : tmpx) {
    X.push_back(p.second);
  }
  for (auto& p : tmpy) {
    Y.push_back(p.second);
  }
  answer(C, X, Y);
}

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