Submission #120293

#	Time	Username	Problem	Language	Result	Execution time	Memory
120293		turbat	Mechanical Doll (IOI18_doll)	C++14	9 / 100	123 ms	9720 KiB

doll

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

int n, m, s, cnt;
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] = -1; 
        else x[node - 1] = a[idx];
        if (idx + p >= n) y[node - 1] = -1;
        else y[node - 1] = a[idx + p];
        return;
    }
    int mid = (l + r) / 2;
    x[node - 1] =  -(node * 2);
    y[node - 1] = -(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;
    if (s == n && a[0] == a.back()) s *= 2;
    x.resize(s - 1);
    y.resize(s - 1);
    c.resize(m + 1);
    for (int i = 0;i <= m;i++) c[i] = -1;
    build(1, 0, s - 1, 0, 1);
    if (n == s) c[A.back()] = 0;
    else y[s - 2] = 0;
    // for (int i = 0;i <= m;i++) cout <<i << ' '<< c[i]<< endl;
    // for (int i = 0;i < s - 1;i++) cout << i + 1<< ' '<< 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: 9 / 18
• Subtask 6: 0 / 56