Submission #597789

#	Time	Username	Problem	Language	Result	Execution time	Memory
597789		TimDee	Mechanical Doll (IOI18_doll)	C++14	77.60 / 100	131 ms	25244 KiB

doll

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

struct tree {
    int n, size;
    vector<int> t, x, y, state;
    void build(int N, int amt) {
        n=N;
        size=1;
        while ((size<<1)<n) size<<=1;
        t.assign(2*size-1,0), x.assign(2*size-1,0), y.assign(2*size-1,0), state.assign(2*size-1,0);
        for (int i=1; i<=size-1; ++i) {
            x[i-1] = -(2*i);
            y[i-1] = -(2*i+1);
        }
        int cnt=0, p=0;
        while (cnt<2*size-amt) {
            if (p>=size-1) {
                if (state[p]) {
                    y[p]=-1;
                } else {
                    x[p]=-1;
                }
                state[p]^=1;
                ++cnt;
                p=0;
                continue;
            }
            if (!state[p]) {
                state[p]^=1;
                p<<=1; ++p;
            } else {
                state[p]^=1;
                ++p; p<<=1;
            }
        }
    }
};

vector<vector<int>> solve1(int n, int m, vector<int>&a, vector<int>&cnt) {
    vector<int> c(m+1),x,y;
        c[0]=a[0];
        vector<tree> v(m+1);
        for (int i=1; i<=m; ++i) v[i].build(cnt[i],cnt[i]);

        int in=0, p=0;
        while (in<n) {
            int ind = a[in];
            while (p<v[ind].size-1) {
                if (!v[ind].state[p]) {
                    v[ind].state[p]^=1;
                    p<<=1;
                    ++p;
                } else {
                    v[ind].state[p]^=1;
                    ++p;
                    p<<=1;
                }
            }
            if (!v[ind].state[p]) {
                v[ind].x[p]= ((++in)<n) ? a[in] : 0;
                v[ind].state[p]^=1;
            } else {
                v[ind].y[p]= ((++in)<n) ? a[in] : 0;
                v[ind].state[p]^=1;
            }
            p=0;
        }

        for(int i=1; i<=m; ++i) {
            int sz=x.size();
            for (auto X:v[i].x) x.push_back( X>=0 ? X : (X-sz) );
            for (auto Y:v[i].y) y.push_back( Y>=0 ? Y : (Y-sz) );
            c[i]=-1-sz;
        }
    vector<vector<int>> r = {c,x,y};
    return r;
}

vector<vector<int>> solve2(int n, int m, vector<int>&a) {
    vector<int> c(m+1,-1), x, y; c[0]=a[0]; if (a.size()%2) a.push_back(-1); a.push_back(0);
    int sz=1; while ((sz<<1)<n) sz<<=1;
    int N=n+(n%2);
    x.assign(sz-1,-1); y.assign(sz-1,-1);
    for (int i=1; 2*i+1<=sz-1; ++i) {
        x[i-1]=-(2*i); y[i-1]=-(2*i+1);
    }
    vector<int> state(2*sz-1,-1);
    for (int i=0; i<sz-1; ++i) state[i]=0;
    int cnt=0; int id=N;
    while (cnt<2*sz) {
        int p=0;
        while (p<sz-1) {
            if (state[p]==0) {
                state[p]^=1;
                p=p*2+2;
            } else {
                state[p]^=1;
                p=p*2+1;
            }
        }
        if (cnt%sz<N/2) {
            if (state[p]==-1) {
                int prv=(p-1)>>1;
                if (state[prv]) y[prv]=-(y.size()+1);
                else x[prv]=-(y.size()+1);
                y.push_back(a[id--]);
                state[p]=1;
            } else {
                x.push_back(a[id--]);
            }
        }
        ++cnt;
    }
    return {c,x,y};
}

void create_circuit(int m, vector<int>a) {
    int n=a.size();
    vector<int> cnt(m+1,0);
    int mx=0;
    for (int i=0; i<n; ++i) {
        cnt[a[i]]++;
        mx=max(mx,cnt[a[i]]);
    }
    if (mx==1) {
        vector<int> c(m+1,0);
        c[0]=a[0];
        for (int i=1; i<n; ++i) {
            c[a[i-1]]=a[i];
        }
        vector<int> x(0), y(0);
        answer(c,x,y);
    } else if (mx==2) {
        vector<vector<int>> next(m+1);
        //vector<int> b=a;
        a.push_back(0);
        for (int i=0; i<n; ++i) next[a[i]].push_back(a[i+1]);
        vector<int> c(m+1);
        c[0]=a[0];
        for (int i=1; i<=m; ++i) {
            c[i]=-i;
        }
        vector<int> x(m,0), y(m,0);
        for (int i=1; i<=m; ++i) {
            if (!next[i].size()) continue;
            x[i-1] = next[i].size()>1 ? next[i][0] : -(i);
            y[i-1] = next[i].size()>1 ? next[i][1] : next[i][0];
        }
        answer(c,x,y);
    } else if (n==16) {
        vector<int> c(m+1,-1); c[0]=a[0];
        vector<int> x(15), y(15);
        for (int i=0;i<7;++i) {x[i]=-(2*i+2); y[i]=-(2*i+3);}
        x[7]=a[1], x[11]=a[2], x[9]=a[3], x[13]=a[4], x[8]=a[5], x[12]=a[6], x[10]=a[7], x[14]=a[8];
        y[7]=a[9], y[11]=a[10], y[9]=a[11], y[13]=a[12], y[8]=a[13], y[12]=a[14], y[10]=a[15], y[14]=0;
        answer(c,x,y);
    } else if (m==1) {

        int size=1;
        while (4*size<n) size<<=1;
        vector<int> x(2*size+1), y(2*size+1), state(2*size+1,0), c = {1, -(2*size)};
        for (int i=1; i<=size-1; ++i) {
            x[i-1] = -(2*i);
            y[i-1] = -(2*i+1);
        }
        x[2*size-1]=-(2*size+1);
        y[2*size-1]=-1;
        x[2*size] = y[2*size] = 1;

        int cnt=0, p=0;
        while (cnt<2*size) {

            //cout<<p<<"->";
            if (p>=size-1) {
                //cout<<"added "<<p<<' '<<cnt<<'\n';
                if (state[p]) {
                    if (cnt<n-1-2*size) y[p]=1;
                    else y[p]=-(2*size);
                } else {
                    if (cnt<n-1-2*size) x[p]=1;
                    else x[p]=-(2*size);
                }
                state[p]^=1;
                ++cnt;
                p=0;
                continue;
            }

            if (!state[p]) {

                state[p]^=1;
                p<<=1; ++p;

            } else {

                state[p]^=1;
                ++p; p<<=1;

            }

        }
        y[2*size-2]=0;
        answer(c,x,y);

    } else {

        vector<vector<int>> f = solve1(n,m,a,cnt);
        vector<vector<int>> s = solve2(n,m,a); //cout<<f[0].size()<<' '<<f[1].size()<<' '<<f[2].size()<<'\n';
        //for (auto x:f[1]) cout<<x<<' '; cout<<'\n';
        //for (auto y:f[2]) cout<<y<<' '; cout<<'\n';
        if (f[1].size()>s[1].size()) swap(f,s);
        answer(f[0],f[1],f[2]);

    }
}

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