Submission #316374

#	Time	Username	Problem	Language	Result	Execution time	Memory
316374		alextodoran	Mechanical Doll (IOI18_doll)	C++17	0 / 100	150 ms	262148 KiB

doll

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

typedef long long ll;

struct XYSwitch
{
    int X, Y;
    bool state;
};

vector <XYSwitch> switches;

int createInfiniteSwitch (int N, int firstPos, int level)
{
    if(level == 0)
    {
        if(N == 0)
        {
            int X = -777777777;
            int Y = -777777777;
            switches.push_back(XYSwitch{X, Y});
            return (int)switches.size() - 1;
        }
        if(N == 1)
        {
            int X = -firstPos;
            int Y = -777777777;
            switches.push_back(XYSwitch{X, Y});
            return (int)switches.size() - 1;
        }
        if(N == 2)
        {
            int X = -firstPos;
            int Y = -(firstPos + 1);
            switches.push_back(XYSwitch{X, Y});
            return (int)switches.size() - 1;
        }
    }
    int L;
    if(N > 0)
    {
        int p2 = 0;
        while((1 << (p2 + 1)) < N)
            p2++;
        L = (1 << p2);
    }
    else
        L = 0;
    int X = createInfiniteSwitch(L, firstPos, level - 1);
    int Y = createInfiniteSwitch(N - L, firstPos + L, level - 1);
    switches.push_back(XYSwitch{X, Y, false});
    return (int)switches.size() - 1;
}

int createFiniteSwitch (int N, int firstPos, int level)
{
    if(level == 0)
    {
        if(N == 0)
        {
            int X = -777777777;
            int Y = 0;
            switches.push_back(XYSwitch{X, Y, false});
            return (int)switches.size() - 1;
        }
        if(N == 1)
        {
            int X = -firstPos;
            int Y = 0;
            switches.push_back(XYSwitch{X, Y, false});
            return (int)switches.size() - 1;
        }
    }
    int L;
    if(N > 0)
    {
        int p2 = 0;
        while((1 << (p2 + 1)) < N)
            p2++;
        L = (1 << p2);
    }
    else
        L = 0;
    int X = createInfiniteSwitch(L, firstPos, level - 1);
    int Y = createFiniteSwitch(N - L, firstPos + L, level - 1);
    switches.push_back(XYSwitch{X, Y, false});
    return (int)switches.size() - 1;
}

vector <int> triggers;

int curr;

bool dfs (int u)
{
    if(u < 0)
    {
        triggers[-u] = curr;
        return true;
    }
    if(u == 0)
        return false;
    switches[u].state ^= 1;
    if(switches[u].state == true)
        return dfs(switches[u].X);
    else
        return dfs(switches[u].Y);
}

void create_circuit(int M, vector <int> A)
{
    int N = A.size();
    switches.clear();
    switches.push_back(XYSwitch{0, 0, false});
    int p2 = 0;
    while((1 << (p2 + 1)) <= N)
        p2++;
    int root = createFiniteSwitch(N, 1, p2 - 1);
    for(int i = 1; i < (int)switches.size(); i++)
    {
        if(switches[i].X == -777777777)
            switches[i].X = root;
        if(switches[i].Y == -777777777)
            switches[i].Y = root;
    }
    triggers.clear();
    triggers.resize(M + 1);
    for(int i = 0; i < N; i++)
    {
        curr = A[i];
        while(true)
        {
            if(dfs(root) == true)
                break;
        }
    }
    vector <int> X(switches.size() - 1), Y(switches.size() - 1), C(M + 1);
    for(int i = 1; i < (int)switches.size(); i++)
    {
        if(switches[i].X < 0)
            X[i - 1] = triggers[-switches[i].X];
        else
            X[i - 1] = -switches[i].X;
        if(switches[i].Y < 0)
            Y[i - 1] = triggers[-switches[i].Y];
        else
            Y[i - 1] = -switches[i].Y;
    }
    C[0] = -root;
    for(int i = 1; i <= M; i++)
        C[i] = root;
    answer(C, X, Y);
}

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