Submission #1186580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186580		HappyCapybara	Mechanical Doll (IOI18_doll)	C++17	47 / 100	43 ms	12072 KiB

doll

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

void create_circuit(int m, vector<int> a){
    int n = a.size();
    int pn = pow(2, floor(log2(n-1))+1);
    vector<int> b = a;
    a = {};
    b.push_back(0);
    while (a.size()+b.size() <= pn) a.push_back(-1);
    for (int i=1; i<=n; i++) a.push_back(b[i]);
    vector<int> v = {0}, w;
    while (v.size() != pn){
        w = {};
        swap(v, w);
        for (int x : w){
            v.push_back(x);
            v.push_back(x + (int) w.size());
        }
    }
    vector<int> c(m+1, -1), x(pn-1), y(pn-1);
    c[0] = b[0];
    for (int i=0; i<pn-1; i++){
        if (2*(i+1) < pn-1){
            x[i] = -2*(i+1);
            y[i] = -2*(i+1)-1;
        }
        else {
            x[i] = a[v[2*(i+1)-pn]];
            y[i] = a[v[2*(i+1)+1-pn]];
        }
    }
    answer(c, x, y);
}

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