Submission #117805

#	Time	Username	Problem	Language	Result	Execution time	Memory
117805		IOrtroiii	Mechanical Doll (IOI18_doll)	C++14	100 / 100	117 ms	11384 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

const int N = 1 << 18;
const int inf = 1e9;

int n, m, sz, lg;
int a[N];
int rev[N];
int id[N];
vector<int> x, y;

int go(int l, int r) {
   if (l == r) {
      if (l >= sz - n) {
         return a[id[l]];
      } else {
         return inf;
      }
   } else {
      int md = (l + r) >> 1;
      int lv = go(l, md);
      int rv = go(md + 1, r);
      if (lv == inf && rv == inf) {
         return inf;
      } else {
         x.push_back(lv);
         y.push_back(rv);
         return -(int) x.size();
      }
   }
}

void create_circuit(int m, vector<int> a) {
   n = a.size();
   ::m = m;
   for (int i = 0; i < n; ++i) {
      ::a[i] = a[i];
   }
   sz = 1, lg = 0;
   while (sz < n) {
      sz <<= 1;
      ++lg;
   }
   for (int i = 0; i < sz; ++i) {
      for (int j = 0; j < lg; ++j) {
         if (i & (1 << j)) {
            rev[i] |= 1 << (lg - 1 - j);
         }
      }
   }
   int tot = 0;
   for (int i = 0; i < sz; ++i) {
      if (rev[i] >= sz - n) {
         id[rev[i]] = ++tot;
      }
   }
   int rt = go(0, sz - 1);
   vector<int> c(m + 1, rt);
   c[0] = a[0];
   for (int i = 0; i < -rt; ++i) {
      if (x[i] == inf) {
         x[i] = rt;
      }
      if (y[i] == inf) {
         y[i] = rt;
      }
   }
   answer(c, x, y);
}

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