Submission #602878

#	Time	Username	Problem	Language	Result	Execution time	Memory
602878		SlavicG	Mechanical Doll (IOI18_doll)	C++17	100 / 100	125 ms	49376 KiB

doll

#include "doll.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 5e6;
vector<int> x(N), y(N);
int idx = 0, n, cc[N];
int NN;
int build(int l, int r) {
    if(NN - 1 - r >= n) return -1;
    if(l == r) return 1;
    int mid = l + r >> 1;
    int i = idx++;
    x[i] = build(l, mid);
    y[i] = build(mid + 1, r);
    return -i - 1;
}

void create_circuit(int m, vector<int> a) {
    a.push_back(0);
    n = a.size();
    vector<int> c(m + 1, -1);
    NN = n; while(__builtin_popcount(NN) != 1) ++NN;
    build(0, NN - 1);
    x.resize(idx);
    y.resize(idx);

    for(int i: a) {
        int node = 0;
        while(true) {
            int nxt = (cc[node] ? y[node] : x[node]);
            if(nxt == 1) {
                if(cc[node] == 1) y[node] = i;
                else x[node] = i;
                cc[node] ^= 1;
                break;
            }
            cc[node] ^= 1;
            node = -nxt - 1;
        }
    }
    answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'int build(int, int)':
doll.cpp:11:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |     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