Submission #120242

#	Time	Username	Problem	Language	Result	Execution time	Memory
120242		turbat	Mechanical Doll (IOI18_doll)	C++14	0 / 100	2 ms	204 KiB

doll

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

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

void build (int node, int l, int r, int idx, int p){
    if (r - l == 1){
        if (idx >= n) x[node] = -1; 
        else x[node] = a[idx];
        if (idx + p >= n) y[node] = -1;
        else y[node] = a[idx + p];
        return;
    }
    int mid = (l + r) / 2;
    x[node] =  -(node * 2);
    y[node] = -(node * 2 + 1);
    build (node * 2, l, mid, idx, p * 2);
    build (node * 2 + 1, l, mid, idx + p, p * 2);
}

void create_circuit(int M, vector<int> A) {
    a = A;
    s = n = A.size();
    m = M;
    while (__builtin_popcount(s) != 1) s += s & -s;
    x.resize(s);
    y.resize(s);
    c.resize(m + 1);
    for (int i = 0;i <= m;i++) c[i] = -1;
    if (n == s) c[A.back()] = 0;
    else y[s - 1] = 0;
    build(1, 0, s - 1, 0, 1);
    // for (int i = 0;i <= m;i++) cout << i << ' ' << c[i]<< endl;
    // for (int i = 1;i < s;i++) cout << i << ' ' << x[i] << ' '<< y[i]<< endl;
    answer(c, x, y);
}   

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