Submission #442732

#	Time	Username	Problem	Language	Result	Execution time	Memory
442732		peijar	Mechanical Doll (IOI18_doll)	C++17	63 / 100	183 ms	14984 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();
  vector<vector<int>> goAfter(nbFixes);
  for (int i = 0; i < nbEtapes; ++i) {
    if (i + 1 < nbEtapes)
      goAfter[ordre[i] - 1].push_back(ordre[i + 1]);
    else
      goAfter[ordre[i] - 1].push_back(0);
  }
  exitFixed.resize(nbFixes + 1);
  exitFixed[0] = ordre[0];
  if (__builtin_popcount(nbEtapes) == 1) {
    vector<int> elem;
    for (int i = 0; i < nbEtapes; ++i)
      elem.push_back(i + 1 < nbEtapes ? ordre[i + 1] : 0);
    if (elem.size() > 1) {
      int r = build(elem);
      for (int i = 1; i <= nbFixes; ++i)
        exitFixed[i] = r;
    } else {
      exitFixed[ordre[0]] = 0;
    }
    answer(exitFixed, exitEven, exitOdd);
    return;
  }

  for (int i = 0; i < nbFixes; ++i) {
    if (goAfter[i].empty())
      continue;
    if (goAfter[i].size() == 1) {
      exitFixed[i + 1] = goAfter[i].front();
      continue;
    }
    exitFixed[i + 1] = build(goAfter[i]);
  }

  answer(exitFixed, exitEven, exitOdd);
}

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