Submission #416672

#	Time	Username	Problem	Language	Result	Execution time	Memory
416672		wiwiho	Mechanical Doll (IOI18_doll)	C++14	47 / 100	171 ms	11148 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>

#define eb emplace_back
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

int n, m;
vector<int> a;
vector<int> x, y;
int s;

vector<bool> state;
int go = 0;
int dfs(int now){
    if(now == 0) return go;
    if(!state[now - 1]){
        state[now - 1] = true;
        x[now - 1] = dfs(-x[now - 1]);
    }
    else{
        state[now - 1] = false;
        y[now - 1] = dfs(-y[now - 1]);
    }
    return -now;
}

void create_circuit(int _m, vector<int> _a){
    m = _m;
    a = _a;
    n = a.size();

    int leaf = 1;
    int s = 1;
    while(leaf * 2 < n){
        leaf *= 2;
        s += leaf;
    }
    x.resize(s);
    y.resize(s);

    for(int i = 1; i <= s; i++){
        if(2 * i <= s) x[i - 1] = - (2 * i);
        if(2 * i + 1 <= s) y[i - 1] = - (2 * i + 1);
    }
    //cerr << leaf * 2 << "\n";
    //printv(x, cerr);
    //printv(y, cerr);

    vector<int> c(m + 1, -1);
    state.resize(s);
    c[0] = a[0];

    for(int i = 0; i < n - 1; i++){
        go = a[i + 1];
        dfs(1);
    }
    for(int i = n - 1; i < leaf * 2 - 1; i++){
        go = -1;
        dfs(1);
        //cerr << "temp\n";
    }
    go = 0;
    dfs(1);

    //printv(x, cerr);
    //printv(y, cerr);

    answer(c, x, y);
}

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