Submission #75123

#	Time	Username	Problem	Language	Result	Execution time	Memory
75123		imeimi2000	Mechanical Doll (IOI18_doll)	C++17	100 / 100	114 ms	10460 KiB

doll

#include "doll.h"

using namespace std;

int n;
int seg[1 << 19];

int bitRev(int x, int n) {
    int r = 0;
    while (n >>= 1) {
        r <<= 1;
        r ^= (x & 1);
        x >>= 1;
    }
    return r;
}

const int inf = 1e9;
void create_circuit(int m, vector<int> A) {
    int sz = 1;
    A.push_back(0);
    n = A.size();
    while (sz < n) sz <<= 1;
    for (int i = 0; i < sz; ++i) seg[i + sz] = inf;
    for (int i = 0, j = 0; i < sz; ++i) {
        int k = bitRev(i, sz);
        if (k < sz - n) continue;
        seg[k + sz] = A[j++];
    }
    int SN = 0;
    vector<int> X, Y;
    for (int i = sz; --i; ) {
        if (seg[i << 1] == seg[i << 1 | 1]) {
            seg[i] = seg[i << 1];
            continue;
        }
        int S = SN++;
        seg[i] = -(S + 1);
        X.push_back(seg[i << 1]);
        Y.push_back(seg[i << 1 | 1]);
    }
    for (int i = 0; i < SN; ++i) {
        if (X[i] == inf) X[i] = seg[1];
        if (Y[i] == inf) Y[i] = seg[1];
    }
    answer(vector<int>(m + 1, seg[1]), X, Y);
}

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