Submission #235681

#	Time	Username	Problem	Language	Result	Execution time	Memory
235681		lyc	Mechanical Doll (IOI18_doll)	C++14	100 / 100	159 ms	12276 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) //cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

const int mxN = 2e5+5;

int M, N;
int D[2*mxN], L[2*mxN], R[2*mxN], state[2*mxN];

int build(int s, int e, int p, int l) {
    int en = p;
    if (l == 1) R[p] = 1;
    else {
        R[p] = -(p+1);
        en = build(max(s,e-l+1),e,-R[p],l>>1);
    }
    if (e-l >= s) {
        if (l == 1) L[p] = 1;
        else {
            L[p] = -(en+1);
            en = build(s,e-l,-L[p],l>>1);
        }
    } else {
        L[p] = -1;
    }
    TRACE(s _ e _ p _ L[p] _ R[p]);
    return en;
}

void simulate(int p, int v) {
    int pos = p;
    for (;;) {
        //TRACE(pos _ state[-pos]);
        state[-pos] = !state[-pos];
        if (state[-pos]) {
            if (L[-pos] > 0) { TRACE(-pos _ "L" _ v); L[-pos] = v; break; }
            else pos = L[-pos];
        } else {
            if (R[-pos] > 0) { TRACE(-pos _ "R" _ v); R[-pos] = v; break; }
            else pos = R[-pos];
        }
    }
}

void create_circuit(int _M, std::vector<int> A) {
    M = _M;
    A.push_back(0);
    N = A.size();
    vector<int> C(M+1,-1);

    int n2 = 1;
    while (n2 < N) n2 <<= 1;
    int S = build(n2-N+1,n2,1,n2>>1);

    for (int& x : A) { simulate(-1,x); }

    vector<int> X(S), Y(S);
    FOR(i,1,S){
        X[i-1] = L[i];
        Y[i-1] = R[i];
        TRACE(i _ X[i-1] _ Y[i-1]);
    }
    answer(C, 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