Submission #295766

#	Time	Username	Problem	Language	Result	Execution time	Memory
295766		Bruteforceman	Mechanical Doll (IOI18_doll)	C++11	37 / 100	269 ms	30800 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; 
  }
  if(abs(b - e) % 2 == 0) ++e;
  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 root, vector <int> v) {
  if(v.empty()) return ; 
  vector <int> order;
  to[root] = -create(1, (1 + v.size()) / 2, order);
  set <int> cont;
  int pt = 0;
  for(int i = 0; i < order.size(); i++) {
    if(cont.count(order[i])) {
      if(i >= order.size() - v.size()) {
        r[order[i]] = v[pt++]; 
      } else {
        r[order[i]] = to[root];
      }
    } else {
      if(i >= order.size() - v.size()) {
        l[order[i]] = v[pt++];
      } else {
        l[order[i]] = to[root];
      }
    }
    cont.insert(order[i]);
  }
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  A.insert(A.begin(), 0);
  A.insert(A.end(), 0);
  for(int i = 1; i < A.size(); i++) {
    g[A[i - 1]].push_back(A[i]);
  }
  for(int i = 0; i <= M; i++) {
    getEdges(i, g[i]);
  }
  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:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i = 0; i < left.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
doll.cpp: In function 'void getEdges(int, std::vector<int>)':
doll.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i = 0; i < order.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
doll.cpp:38:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |       if(i >= order.size() - v.size()) {
      |          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:44:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       if(i >= order.size() - v.size()) {
      |          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 1; i < A.size(); i++) {
      |                  ~~^~~~~~~~~~
doll.cpp:55:7: warning: unused variable 'N' [-Wunused-variable]
   55 |   int N = A.size();
      |       ^

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