Submission #172243

#	Time	Username	Problem	Language	Result	Execution time	Memory
172243		AlexLuchianov	Mechanical Doll (IOI18_doll)	C++14	100 / 100	127 ms	11624 KiB

doll

#include "doll.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

#define ll long long

int const nmax = 800000;
std::vector<int> v;
std::vector<int> soltriggers;
std::vector<int> sol;

int rev(int n, int number){
  int p = 0;
  while((1 << p) < n)
    p++;
  int result = 0;
  for(int i = 0; i < p; i++)
    if(0 < (number & (1 << i)))
      result |= (1 << (p - 1 - i));
  return result;
}

std::vector<int> left, right;
int devices = 0;

int isempty[1 + nmax];

void precompute(int node, int from, int to){
  if(from < to){
    int mid = (from + to) / 2;
    precompute(node * 2, from, mid);
    precompute(node * 2 + 1, mid + 1, to);
    isempty[node] = isempty[node * 2] | isempty[node * 2 + 1];
  } else
    isempty[node] = (0 <= v[from]);
}

int build(int node, int from, int to){
  if(isempty[node] == 0)
    return -1;
  else if(from < to){
    ++devices;
    int id = devices;
    left.push_back(0);
    right.push_back(0);
    int mid = (from + to) / 2;
    int lft = build(node * 2, from, mid);
    int rght = build(node * 2 + 1, mid + 1, to);
    left[id - 1] = lft;
    right[id - 1] = rght;
    return -id;
  } else
    return v[from];
}
void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> initv;
  for(int i = 0; i < N; i++)
    initv.push_back(A[i]);
  initv.push_back(0);
  soltriggers.resize(1 + M);

  int n = 1;
  while(n < initv.size())
    n *= 2;
  int unused = n - initv.size();
  v.resize(n);
  int ptr = 0;
  for(int i = 0; i < n; i++)
    v[i] = -1;
  for(int i = 0; i < n; i++) {
    int pos = rev(n, i);
    if(unused <= pos)
      v[pos] = initv[ptr++];
  }
  for(int i = 0;i <= M; i++)
    soltriggers[i] = -1;
  precompute(1, 0, n - 1);
  soltriggers[0] = build(1, 0, n - 1);

  answer(soltriggers, left, right);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:66:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   while(n < initv.size())
      |         ~~^~~~~~~~~~~~~~

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