Submission #1277913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277913		monval	Mechanical Doll (IOI18_doll)	C++20	18 / 100	53 ms	9380 KiB

doll

#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

extern void answer(vector<int> C, vector<int> X, vector<int> Y);

void build_tree(int n, int k, int level, int binary, int& switches, vector<int>& X, vector<int>& Y, vector<tuple<int, bool, int> >::iterator& output){
  switches++;
  X.push_back(0);
  Y.push_back(0);
  if(k == 1){
    *output = make_tuple(switches, true, binary + (1 << level));
    output++;
    if(n == 1){
      X[switches - 1] = -1;
    }else{
      *output = make_tuple(switches, false, binary);
      output++;
    }
  }else{
    int current_switch = switches;
    if(n <= 1 << (k - 1)){
      Y[switches - 1] = -(switches + 1);
      build_tree(n, k - 1, level + 1, binary + (1 << level), switches, X, Y, output);
      X[current_switch - 1] = -1;
    }else{
      Y[switches - 1] = -(switches + 1);
      build_tree(1 << (k - 1), k - 1, level + 1, binary + (1 << level), switches, X, Y, output);
      X[current_switch - 1] = -(switches + 1);
      build_tree(n - (1 << (k - 1)), k - 1, level + 1, binary, switches, X, Y, output);
    }
  }
}

void create_circuit(int M, vector<int> A) {
  int N = A.size();
  vector<int> C(M + 1);
  vector<int> X;
  vector<int> Y;
  vector<tuple<int, bool, int> > outputs(N);
  C[0] = 1;
  for(int i = 1; i <= M; i++){
    C[i] = -1;
  }
  int switches = 0;
  int log_two = 0;
  while(1 << log_two < N){
    log_two++;
  }
  auto output = outputs.begin();
  build_tree(N, log_two, 0, 0, switches, X, Y, output);
  auto compare = [](tuple<int, bool, int> a, tuple<int, bool, int> b){
    return get<2>(a) < get<2>(b);
  };
  sort(outputs.begin(), outputs.end(), compare);
  A.push_back(0);
  for(int i = 0; i < N; i++){
    if(!get<1>(outputs[i])){
      X[get<0>(outputs[i]) - 1] = A[i + 1];
    }else{
      Y[get<0>(outputs[i]) - 1] = A[i + 1];
    }
  }
  answer(C, X, Y);
}

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