Submission #218191

#	Time	Username	Problem	Language	Result	Execution time	Memory
218191		anonymous	Mechanical Doll (IOI18_doll)	C++14	100 / 100	146 ms	10124 KiB

doll

#include "doll.h"
#include<vector>
#include<iostream>
#include<cassert>
#define MAXN 200105
using namespace std;
int N, L, V=-1, id;
bool state[MAXN];
vector<int> X, Y, C, Seq;

int build(int x, int d) {
    if (x == 1 && d == 0) {
        return(69);
    } else if (x == 0) {return(-1);}
    assert(d > 0);
    int cur = V;
    V--;
    X[-cur-1] = build(x-min(x,(1<<(d-1))), d-1);
    Y[-cur-1] = build(min(x,(1<<(d-1))), d-1);
    return(cur);
}

int log(int x) {
    return(x <= 1 ? 0 : log(x/2) + 1);
}

void simulate(int u) {
    if (id == N+1) {return;}
    if (state[-u] == 0) {
        state[-u] = 1;
        if (X[-u-1] == 69) {
            X[-u-1] = Seq[id];
            id++;
            simulate(-1);
        } else {
            simulate(X[-u-1]);
        }
    } else {
        state[-u] = 0;
        if (Y[-u-1] == 69) {
            Y[-u-1] = Seq[id];
            id++;
            simulate(-1);
        } else {
            simulate(Y[-u-1]);
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
  N = A.size(), L = log(N+1);
  if ((1<<L) < N+1) {L++;}
  for (int i=0; i<=M; i++) {
    C.push_back(-1);
  }
  for (int i=0; i<N+L; i++) {
    X.push_back(0);
    Y.push_back(0);
  }
  Seq = A;
  Seq.push_back(0);
  build(N+1, L);
  while (X.back() == 0 && Y.back() == 0) {
    X.pop_back();
    Y.pop_back();
  }
  simulate(-1);
  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