Submission #1244829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244829		jeroenodb	Mechanical Doll (IOI18_doll)	C++20	100 / 100	78 ms	7776 KiB

doll

#include "doll.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) begin(x),end(x)
const int oo = 1e9;
void create_circuit(int M, std::vector<int> A) {
    int n = A.size();
    
    int m = M;
    vi c(m + 1,-1);
    vi x,y;
    int at=0;
    auto nwnode = [&]() {
        x.push_back(-oo);
        y.push_back(-oo);
        return at++;
    };

    auto swi = [&](int at) {
        return -(at+1);
    };
    auto buildseg= [&](auto&& self,int d) {
        if(d==0) {
            return -oo;
        }
        int at = nwnode();
        int l = self(self,d-1);
        int r = self(self,d-1);
        x[at]=l;
        y[at]=r;
        return swi(at);
    };
    int pw = 1, lg=0;
    while(pw<n) pw*=2,lg++;
    vi lgnode = {};
    for(int j=lg;j>=0;--j) {
        int mynode = nwnode();
        if(1<<j & n) {
            x[mynode] = buildseg(buildseg, j);
        } else x[mynode]=-1;
        if(j!=lg) y[lgnode.back()]= swi(mynode);
        y[mynode]=0;
        lgnode.push_back(mynode);
    }
    int cur=0;
    vector<bool> state(x.size());
    auto place = [&](auto&& self, int at) {

        if(state[at]) {
            state[at]=!state[at];

            if(y[at]==-oo) {
                y[at]=A[cur++];
                return;
            } else if(y[at]>=0) {
                assert(false);
            }
            self(self,swi(y[at]));
        } else {
            state[at]=!state[at];

            if(x[at]==-oo) {
                x[at]=A[cur++];
                return;
            } else if(x[at]>=0) {
                assert(false);
            }
            self(self,swi(x[at]));
        }
    };
    for(int i=0;i<n;++i) place(place,0);
    answer(c,x,y);
    cerr << x.size() << '\n';
    

  
}

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