Submission #602864

#	Time	Username	Problem	Language	Result	Execution time	Memory
602864		SlavicG	Mechanical Doll (IOI18_doll)	C++17	0 / 100	20 ms	39460 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 build(int l, int r) {
    if(l >= 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);
    int N = n; while(__builtin_popcount(N) != 1) ++N;

    build(0, N - 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:13:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int mid = l + r >> 1;
      |               ~~^~~

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