Submission #442756

#	Time	Username	Problem	Language	Result	Execution time	Memory
442756		peijar	Mechanical Doll (IOI18_doll)	C++17	47 / 100	156 ms	13736 KiB

doll

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

vector<int> exitFixed;
vector<int> exitEven, exitOdd;
int nbSwaps;

bool allRoot(vector<int> e) {
  for (auto v : e)
    if (v != -1)
      return false;
  return true;
}
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);
  if (allRoot(even))
    exitEven[ret - 1] = -1;
  else
    exitEven[ret - 1] = build(even);
  if (allRoot(odd))
    exitOdd[ret - 1] = -1;
  else 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];
  if (nbEtapes == 1) {
    exitFixed[ordre[0]] = 0;
    answer(exitFixed, exitEven, exitOdd);
    return;
  }

  int k = 0;
  while ((1LL << (k + 1)) < nbEtapes)
    k++;
  int restant = (1 << (k + 1)) - nbEtapes;
  if ((1 << k) == nbEtapes)
    restant = 0;
  cerr << "Val : " << k << ' ' << restant << endl;
  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);
  cerr << "count switch : " << exitEven.size() << endl;
  // assert((int)exitEven.size() <= nbEtapes + (int)log2(nbEtapes));
  assert(nbSwaps <= 2 * nbEtapes);
  answer(exitFixed, exitEven, exitOdd);
}

• 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