Submission #1244769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244769		jeroenodb	Mechanical Doll (IOI18_doll)	C++20	43 / 100	78 ms	13836 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);
    c[0] = -1;
    vi x,y;
    int at=0;
    bool bad=0;
        auto nwnode = [&]() {
        x.push_back(-oo);
        y.push_back(-oo);
        return at++;
    };
    auto swi = [&](int at) {
        return -(at+1);
    };

    {
    vvi nxt(m+1);
    for(int i=0;i+1<n;++i) {
        nxt[A[i]].push_back(A[i+1]);
    }
    nxt[A.back()].push_back(0);
    nxt[0].push_back(A[0]);


    auto buildseg = [&](int my, vi to) {
        if(size(to)==0) {
            c[my]=0;
            return;
        }else if(size(to)==1) {
            c[my]=to[0];
            return;
        }else  if(size(to)==2) {
            int sw = nwnode();
            c[my]=swi(sw);
            x[sw]=to[0];
            y[sw]=to[1];

        } else bad=1;
        
    };
    for(int i=0;i<=m;++i) {
        buildseg(i,nxt[i]);
    }
    }
    if(bad) {
        fill(all(c),-1);
        x.clear();
        y.clear();
        at=0;
        A.push_back(0);
        auto buildsegtree = [&](vi dest) {
            int pw=1;
            int dep=0;
            while(pw<dest.size()) pw*=2, dep++;
            {
                int last = dest.back();
                dest.pop_back();
                while(dest.size()+1!=pw) {
                    dest.push_back(swi(at));
                }
                dest.push_back(last);
            }
            vector<bool> state(pw);
            x.resize(pw-1);
            y.resize(pw-1);
            for(int i=0;i<pw-1;++i) {
                x[i] = swi(i*2+1);
                y[i] = swi(i*2+2);
            }
            auto place = [&](auto&& self, int at, int d, int to) {
                if(d==dep-1) {
                    if(state[at]) y[at]=to;
                    else x[at]=to;
                    state[at]=!state[at];
                    return;
                } 
                self(self,at*2+1 + state[at],d+1,to);
                state[at]=!state[at];

            };
            for(int i=0;i<pw;++i) {
                place(place,0,0,dest[i]);
            }

            

        };
        buildsegtree(A);

    }
    answer(c,x,y);
    

  
}

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