Submission #442753

#	Time	Username	Problem	Language	Result	Execution time	Memory
442753		peijar	Mechanical Doll (IOI18_doll)	C++17	0 / 100	1 ms	204 KiB

doll

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

vector<int> exitFixed;
vector<int> exitEven, exitOdd;
int nbSwaps;
int build(vector<int> elements) {
  int nbElem = elements.size();
  assert(nbElem > 1);
  if (nbElem == 2) {
    ++nbSwaps;
    exitEven.push_back(elements[0]);
    exitOdd.push_back(elements[1]);
    return -nbSwaps;
  }

  vector<int> even, odd;
  for (int i = 0; i < nbElem; ++i)
    (i % 2 ? odd : even).push_back(elements[i]);
  int ret = ++nbSwaps;

  if (nbElem % 2) {
    odd.push_back(even.back());
    even.back() = -ret;
  }
  assert((int)odd.size() < nbElem);
  exitEven.push_back(-1e9);
  exitOdd.push_back(-1e9);
  exitEven[ret - 1] = build(even);
  if (odd.size() > 1)
    exitOdd[ret - 1] = build(odd);
  else
    exitOdd[ret - 1] = odd.back();
  return -ret;
}

void create_circuit(int nbFixes, vector<int> ordre) {
  int nbEtapes = ordre.size();
  exitFixed.resize(nbFixes + 1);
  exitFixed[0] = ordre[0];

  int k = 0;
  while ((1LL << k) <= nbEtapes)
    k++;
  int restant = (1 << (k + 1)) - nbEtapes;
  vector<int> toBuild;
  while (restant--)
    toBuild.push_back(-1);
  for (int i = 0; i < nbEtapes; ++i)
    toBuild.push_back(i + 1 < nbEtapes ? ordre[i + 1] : 0);
  for (int i = 1; i <= nbFixes; ++i)
    exitFixed[i] = -1;
  build(toBuild);

  answer(exitFixed, exitEven, exitOdd);
}

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