Submission #296156

#	Time	Username	Problem	Language	Result	Execution time	Memory
296156		Bruteforceman	Mechanical Doll (IOI18_doll)	C++11	100 / 100	181 ms	27672 KiB

doll

#include "bits/stdc++.h"
#include "doll.h"
using namespace std;
const int maxn = 5e5 + 10;
vector <int> g[maxn];
int l[maxn], r[maxn];
bool leaf[maxn];
int to[maxn];
int node = 0;

int create(int b, int e, vector <int> &order) {
  int cur = ++node;
  if(b == e) {
    leaf[cur] = true;
    order.push_back(cur);
    order.push_back(cur);
    return cur; 
  }
  int mid = (b + e) >> 1;
  vector <int> left, right;
  l[cur] = create(b, mid, left);
  r[cur] = create(mid + 1, e, right);
  for(int i = 0; i < left.size(); i++) {
    order.push_back(left[i]);
    order.push_back(right[i]);
  }
  return cur;
}

void getEdges(int M, vector <int> arr) {
  int sz = arr.size();
  int bit = __lg(sz) + 1;
  node = bit;
  vector <int> order;
  leaf[1] = true;
  order.push_back(1);
  order.push_back(1);
  for(int i = 1; i < bit; i++) {
    int cur = i + 1;
    r[cur] = i;
    vector <int> v;
    if((sz >> i) & 1) {
      l[cur] = create(1, 1 << (i - 1), v);
    } else {
      l[cur] = bit;
      v.resize(1 << i);
    }
    vector <int> aux;
    for(int i = 0; i < v.size(); i++) {
      aux.push_back(v[i]);
      aux.push_back(order[i]);
    }
    order = aux;
  }
  set <int> cont;
  int pt = 0;
  for(int i = 0; i < order.size(); i++) {
    if(order[i] == 0) continue;
    if(cont.count(order[i])) {
      if(pt < arr.size()) {
        r[order[i]] = arr[pt++]; 
      } else {
        r[order[i]] = -bit;
      }
    } else {
      if(pt < arr.size()) {
        l[order[i]] = arr[pt++];
      } else {
        l[order[i]] = -bit;
      }
    }
    cont.insert(order[i]);
  }
  r[1] = 0; 
  for(int i = 0; i <= M; i++) to[i] = -bit;
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  getEdges(M, A);
  vector <int> C(M + 1);
  vector <int> X (node), Y (node);
  for(int i = 0; i <= M; i++) {
    C[i] = to[i];
  }
  for(int i = 1; i <= node; i++) {
    if(leaf[i]) {
      X[i - 1] = l[i];
      Y[i - 1] = r[i];
    } else {
      X[i - 1] = -l[i];
      Y[i - 1] = -r[i];
    }
  }
  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'int create(int, int, std::vector<int>&)':
doll.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i = 0; i < left.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
doll.cpp: In function 'void getEdges(int, std::vector<int>)':
doll.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
doll.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i = 0; i < order.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
doll.cpp:60:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |       if(pt < arr.size()) {
      |          ~~~^~~~~~~~~~~~
doll.cpp:66:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |       if(pt < arr.size()) {
      |          ~~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:79:7: warning: unused variable 'N' [-Wunused-variable]
   79 |   int N = A.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