Submission #279496

#	Time	Username	Problem	Language	Result	Execution time	Memory
279496		hamerin	Mechanical Doll (IOI18_doll)	C++17	100 / 100	174 ms	10036 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

int sn = 0;
vector<int> C, X, Y;

const int PINF = numeric_limits<int>::max();
const int NINF = numeric_limits<int>::min();

const bool DEBUG = false;

void construct(int N, int d, int cd, int idx, int t) {
    if (DEBUG) cout << N << " " << d << " " << cd << " " << idx << " " << t << endl;
    if (t == 0) {
        ++sn;
        C[idx] = -1;
        X.emplace_back(PINF);
        Y.emplace_back(PINF);

        int K = 1;
        while (K <= N) K <<= 1;
        K >>= 1;

        int psn = sn;
        if (K == N) {
            construct(N >> 1, d, cd + 1, psn - 1, 2);
            construct(N >> 1, d, cd + 1, psn - 1, 4);
        } else {
            construct(K, d, cd + 1, psn - 1, 2);
            construct(N - K, d, cd + 1, psn - 1, 1);
        }
    }

    if (t == 2 || t == 4) {
        if (N == 1) return;

        ++sn;
        if (t == 2) X[idx] = -sn;
        if (t == 4) Y[idx] = -sn;

        X.emplace_back(PINF);
        Y.emplace_back(PINF);

        int psn = sn;
        construct(N >> 1, d, cd + 1, psn - 1, 2);
        construct(N >> 1, d, cd + 1, psn - 1, 4);
    }

    if (t == 1) {
        int K = 1, c = 0;
        while (K <= N) K <<= 1, ++c;
        K >>= 1, --c;

        ++sn;
        Y[idx] = -sn;

        int psn = sn;
        if (c + cd == d) {
            if(N != K) {
                X.emplace_back(PINF);
                Y.emplace_back(PINF);
                construct(K, d, cd + 1, psn - 1, 2);
                construct(N - K, d, cd + 1, psn - 1, 1);
            } else {
                X.emplace_back(-1);
                Y.emplace_back(PINF);
                construct(N, d, cd + 1, psn - 1, 4);
            }
        } else {
            X.emplace_back(-1);
            Y.emplace_back(PINF);
            construct(N, d, cd + 1, psn - 1, 1);
        }
    }
}

void fillc(int v, const vector<int>& nxt) {
    int N = nxt.size();

    vector<bool> swState(sn);
    int ptr = 0;
    for (int i = 0; i < N; i++) {
        int x = C[v];

        if (DEBUG) {
            cout << endl;
            cout << "ptr: " << ptr << endl;
        }

        while (true) {
            x = -1 - x;
            if (DEBUG) cout << x << " " << flush;
            if (!swState[x]) {
                if (DEBUG) cout << "X " << flush;
                swState[x] = !swState[x];
                if (X[x] != PINF)
                    x = X[x];
                else {
                    X[x] = nxt[ptr];
                    ++ptr;
                    break;
                }
            } else {
                if (DEBUG) cout << "Y " << flush;
                swState[x] = !swState[x];
                if (Y[x] != PINF)
                    x = Y[x];
                else {
                    Y[x] = nxt[ptr];
                    ++ptr;
                    break;
                }
            }
        }
    }
    if (DEBUG) cout << endl
                    << endl;
}

bool destruct(int h) {
    if (h >= -1) return false;
    if (h == NINF) h = -1;
    h = -1 - h;
    if (X[h] == -1 && Y[h] == -1) return true;

    if (destruct(X[h])) X[h] = -1;
    if (destruct(Y[h])) Y[h] = -1;

    if (X[h] == -1 && Y[h] == -1)
        return true;
    else
        return false;
}

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    if (N == 1) {
        C.resize(M + 1);
        C[0] = A[0];
        C[A[0]] = 0;
        answer(C, X, Y);
        return;
    }

    C.resize(M + 1);
    C[0] = A[0];

    A.emplace_back(0);
    A.erase(A.begin(), A.begin() + 1);

    int K = 1, d = 0;
    while (K <= N) K <<= 1, ++d;

    construct(N, d, 1, C[0], 0);
    fillc(C[0], A);

    for (int i = 1; i <= M; i++) C[i] = -1;
    destruct(NINF);

    K = X.size();
    vector<int> Xret, Yret;

    vector<int> alive;
    for (int i = 0; i < K; i++) {
        if (X[i] == -1 && Y[i] == -1) continue;
        alive.emplace_back(i);
    }

    for (int i = 0; i < K; i++) {
        if (X[i] == -1 && Y[i] == -1) continue;

        if (X[i] < 0) {
            Xret.emplace_back(-1 - (lower_bound(iterall(alive), -1 - X[i]) - alive.begin()));
        } else {
            Xret.emplace_back(X[i]);
        }

        if (Y[i] < 0) {
            Yret.emplace_back(-1 - (lower_bound(iterall(alive), -1 - Y[i]) - alive.begin()));
        } else {
            Yret.emplace_back(Y[i]);
        }
    }

    answer(C, Xret, Yret);
}

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