Submission #212622

#	Time	Username	Problem	Language	Result	Execution time	Memory
212622		MarcoMeijer	Mechanical Doll (IOI18_doll)	C++14	100 / 100	174 ms	10736 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, root;
vi c, x, y, a, state;
 
int LOG2(int _X) {
  int cur=1, cnt=0;
  while(1) {
    if(cur >= _X) return cnt;
    cnt++;
    cur *= 2;
  }
}
int createTriangle(int size) {
  if(size == 0) return 0;
  int i=s++;
  int id = -s;
  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]) {
    state[u] = !state[u];
    if(y[u] == 0) y[u] = value;
    else setTriangle(y[u], value);
  } else {
    state[u] = !state[u];
    if(x[u] == 0) x[u] = value;
    else setTriangle(x[u], value);
  }
}
void create(int size) {
  int l2 = LOG2(size)+1;
  s = l2;
  root = -s;
  REV(i,0,l2) {
    int u  = i;
    int id = -u-1;
    int nx, ny;
    if(i == 0) ny = 0;
    else ny = id+1;
    if(size&(1<<i)) {
      nx = createTriangle(i);
    } else {
      nx = root;
    }
    x[u] = nx;
    y[u] = ny;
  }
}
 
void create_circuit(int m, vi A) {
  a = A;
  s = 0;
  n = a.size();
  c.clear(); x.clear(); y.clear(); state.clear();
  int mx=3e5;
  x.resize(mx);
  y.resize(mx);
  state.resize(mx);
  RE(i,mx) state[i]=0;
 
  create(n);
  RE(i,n) setTriangle(root, a[i]);
 
  c.resize(m+1);
  RE(i,m+1) c[i] = root;

  x.resize(s);
  y.resize(s);
 
  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