Submission #1277925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277925		monval	Mechanical Doll (IOI18_doll)	C++17	0 / 100	1 ms	332 KiB

doll

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

using namespace std;

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

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] = A[0];
  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();
  forward_list<tuple<int, int, int, int, int, bool> > build_tree = {make_tuple(N, log_two, 0, 0, 0, false)};
  while(!build_tree.empty()){
    int n, k, level, binary, parent;
    bool parent_branch;
    tie(n, k, level, binary, parent, parent_branch) = *build_tree.begin();
    build_tree.pop_front();
    switches++;
    X.push_back(0);
    Y.push_back(0);
    if(!parent_branch){
      X[parent - 1] = -(switches);
    }else{
      Y[parent - 1] = -(switches);
    }
    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{
      if(n <= 1 << (k - 1)){
        X[switches - 1] = -1;
        build_tree.push_front(make_tuple(n, k - 1, level + 1, binary + (1 << level), switches, true));        
      }else{
        build_tree.push_front(make_tuple(n - (1 << (k - 1)), k - 1, level + 1, binary, switches, false));
        build_tree.push_front(make_tuple(1 << (k - 1), k - 1, level + 1, binary + (1 << level), switches, true));
      }
    }
  }
  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: 0 / 18
• Subtask 6: 0 / 56