Submission #585805

#	Time	Username	Problem	Language	Result	Execution time	Memory
585805		Vanilla	Mechanical Doll (IOI18_doll)	C++17	37 / 100	96 ms	10416 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
const int maxn = 2e5 + 2;
int ord[maxn * 2]; // ord[i] -> order of switch -i
int state [maxn * 2]; 
int ct = 0;
int depth;

// void bt (int u, int dp = 1) {
//   if (u == depth) {
//     ord[u] = ct++;
//     return;
//   }
//   bt(u * 2 + state[u], dp + 1);
//   state[u] ^=1;
  
// }

void create_circuit(int m, vector<int> a) {
  int n = a.size();
  vector<int> c(m + 1);
  for (int i = 0; i < 30; i++){
    if ((1 << i) > n) {
      depth = i;
      break;
    }
  }
  int k = (1 << depth);
  vector<int> x(k, -1e9), y(k, -1e9);
  for (int i = 0; i <= m; i++){
    c[i] = -1;
  }
  for (int i = 0; i < n; i++){
    int node = 1;
    for (int j = 1; j < depth; j++) {
      x[node] = -node * 2;
      y[node] = -(node * 2 + 1);
      state[node]^=1;
      node = node * 2 + !state[node];
    }
    if (x[node] == -1e9) {
      x[node] = a[i];
    }
    else {
      y[node] = a[i];
    }
  }
  for (int i = 0; i < k; i++){
    if (x[i] == -1e9) x[i] = -1;
    if (y[i] == -1e9) y[i] = -1;
  }
  y[k - 1] = 0;
  x.erase(x.begin());
  y.erase(y.begin());
  // for (int i = 0; i <= m; i++){
  //   cout << i << " " << c[i] << "\n";
  // }
  // cout << "\n";
  // for (int i = 0; i < k - 1; i++){
  //   cout << -(i + 1) << " " << x[i] << " " << y[i] << "\n";
  // }
  answer(c, x, y);

}

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