Submission #212326

#	Time	Username	Problem	Language	Result	Execution time	Memory
212326		MarcoMeijer	Mechanical Doll (IOI18_doll)	C++14	37 / 100	212 ms	11420 KiB

doll

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

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, s;
vi c, x, y, a, state;

int LOG2(int X) {
  RE(i,30) if((1<<i) >= X) return i;
}
int createTriangle(int size) {
  if(size == 0) return 0;
  int i= s;
  s++;
  int id= -s;
  x.pb(0);
  y.pb(0);
  state.pb(0);
  int nx = createTriangle(size-1);
  int ny = createTriangle(size-1);
  x[i] = nx;
  y[i] = ny;
  return id;
}
void setTriangle(int u, int value) {
  u = -1-u;
  if(state[u]) {
    if(y[u] == 0) y[u] = value;
    else setTriangle(y[u], value);
  } else {
    if(x[u] == 0) x[u] = value;
    else setTriangle(x[u], value);
  }
  state[u] = !state[u];
}

void create_circuit(int m, vi A) {
  a = A;
  s = 0;
  a.push_back(0);
  n = a.size();
  c.clear(); x.clear(); y.clear(); state.clear();

  int l2 = LOG2(n);
  int root = createTriangle(l2);
  int empty = (1<<l2) - n;
  RE(i,empty) setTriangle(root,root);
  RE(i,n) setTriangle(root, a[i]);

  c.resize(m+1);
  RE(i,m+1) c[i] = root;

  answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'int LOG2(int)':
doll.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^

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