Submission #286276

#	Time	Username	Problem	Language	Result	Execution time	Memory
286276		ne4eHbKa	Mechanical Doll (IOI18_doll)	C++17	47 / 100	177 ms	8940 KiB

doll

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

namespace solution {

vi c, x, y;
int s;
vector<bool> e;

int generate_switch(int p) {
    int i = s++;
    x.push_back(0);
    y.push_back(0);
    e.push_back(false);
    if(p) {
        x[i] = generate_switch(p - 1);
        y[i] = generate_switch(p - 1);
    }
    return -(i + 1);
}

void set_exit(int p, int v, int i = 0) {
    int &j = (e[i] ? y : x)[i];
    e[i] = !e[i];
    if(p) {
        set_exit(p - 1, v, -(j + 1));
    } else {
        j = v;
    }
}

}

void create_circuit (int m, vi a) {
    using namespace solution;
    int n = a.size();
    s = 0;
    e.clear(); e.reserve(n * 4);
    x.clear(); x.reserve(n * 4);
    y.clear(); y.reserve(n * 4);
    if(n == 1) {
        c.assign(m + 1, 0);
        c[0] = a[0];
        answer(c, x, y);
        return;
    }
    int p = 0;
    for(; 1 << p < n; ++p);
    --p;
    generate_switch(p);
    c.assign(m + 1, -1);
    c[0] = a[0];
    int u = 1 << p + 1;
    for(int i = 1; i < n; ++i) {
        --u;
        set_exit(p, a[i]);
    }
    while(u > 1) {
        --u;
        set_exit(p, -1);
    }
    set_exit(p, 0);
    answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:55:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   55 |     int u = 1 << p + 1;
      |                  ~~^~~

• 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