Submission #1011207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011207		boris_mihov	Mechanical Doll (IOI18_doll)	C++17	100 / 100	95 ms	12496 KiB

doll

#include "doll.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 400000 + 10;
const int INF  = 1e9;

int n, m, cnt;
std::vector <int> a, c, x, y;

int build(int l, int r, int excess)
{
    if (r < excess)
    {
        return -1;
    }

    if (l == r)
    {
        return 0;
    }

    int node = ++cnt;
    x.push_back(0);
    y.push_back(0);
    int mid = l + r >> 1;
    x[node - 1] = build(l, mid, excess);
    y[node - 1] = build(mid + 1, r, excess);
    return -node;
}

bool state[MAXN];
bool push(int node, int value)
{
    if (state[node] ? (y[node - 1] == -1) : (x[node - 1] == -1))
    {
        state[node] ^= 1;
        return false;
    }
    
    if (state[node] ? (y[node - 1] == 0) : (x[node - 1] == 0))
    {
        if (state[node]) y[node - 1] = value;
        else x[node - 1] = value;
        state[node] ^= 1;
        return true;
    }

    if (state[node])
    {
        bool res = push(-y[node - 1], value);
        state[node] ^= 1;
        return res;
    } else
    {
        bool res = push(-x[node - 1], value);
        state[node] ^= 1;
        return res;
    }
}

void create_circuit(int M, std::vector <int> A)
{
    a = A;
    m = M;
    a.push_back(0);
    int bits = 0;
    int n = a.size();
    while ((1 << bits) < n)
    {
        bits++;
    }

    build(0, (1 << bits) - 1, (1 << bits) - n);
    for (int i = 0 ; i < n ; ++i)
    {
        while (!push(1, a[i]));
    }

    std::vector <int> c(m + 1, -1);
    answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'int build(int, int, int)':
doll.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = l + r >> 1;
      |               ~~^~~

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