Submission #962092

#	Time	Username	Problem	Language	Result	Execution time	Memory
962092		yellowtoad	Mechanical Doll (IOI18_doll)	C++17	100 / 100	98 ms	12888 KiB

doll

#include "doll.h"
#include <iostream>
using namespace std;

int n, idx, b[500010], cnt, cnnt;
vector<int> a, edge[2];

void run(int id, int x, int y) {
  int mid = (x+y)/2;
  if (b[id] == 0) {
    b[id] = 1;
    if (n < mid+1) {
      edge[0][id-1] = -1;
      return;
    }
    if (mid+1 == y) {
      edge[0][id-1] = a[cnnt++];
      return;
    }
    if (edge[0][id-1] == 1e9) {
      edge[0].push_back(1e9);
      edge[1].push_back(1e9);
      edge[0][id-1] = --cnt;
    }
    run(-edge[0][id-1],mid+1,y);
  } else {
    b[id] = 0;
    if (mid+1 == y) {
      edge[1][id-1] = a[cnnt++];
      return;
    }
    if (edge[1][id-1] == 1e9) {
      edge[0].push_back(1e9);
      edge[1].push_back(1e9);
      edge[1][id-1] = --cnt;
    }
    run(-edge[1][id-1],x,mid);
  }
}

void create_circuit(int m, std::vector<int> A) {
  a = A;
  a.push_back(0);
  n = a.size();
  vector<int> C(m+1,-1);
  while ((1<<(idx+1)) < n) idx++;
  edge[0].push_back(1e9);
  edge[1].push_back(1e9);
  cnt = -1;
  for (int i = 1; i <= (1<<(idx+1)); i++) run(1,1,(1<<(idx+1)));
  answer(C,edge[0],edge[1]);
}

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