Submission #643446

#	Time	Username	Problem	Language	Result	Execution time	Memory
643446		cologne	Broken Device 2 (JOI22_device2)	C++17	100 / 100	75 ms	2888 KiB

Anna

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

namespace
{
    const int MAX = 140;
    bool inited = false;
    vector<long long> D(MAX + 1);
    void init()
    {
        if (inited)
            return;
        inited = true;
        D[0] = 1, D[1] = 1, D[2] = 2;
        for (int i = 3; i < MAX; i++)
            D[i] = D[i - 2] + D[i - 3] + 1;
    }
}

int Declare()
{
    init();
    return MAX;
}

pair<vector<int>, vector<int>> Asolve(int sz, long long A)
{
    vector<int> U, V;

    int lst = 0;
    if (A >= D[sz - 1])
    {
        U.push_back(1);
        V.push_back(1);
        A -= D[sz - 1];
        lst = 1;
    }
    else
    {
        U.push_back(0);
        V.push_back(0);
        lst = 0;
    }
    --sz;
    for (int i = 0; i < sz; i++)
        V.push_back(1 - V.back());

    while (sz)
    {
        if (A == 0)
        {
            for (int i = 0; i < sz; i++)
                U.push_back(1 - U.back());
            sz = 0;
            break;
        }
        --A;

        if (lst == 1)
        {
            if (A >= (sz >= 3 ? D[sz - 3] : 0))
            {
                for (int i = 0; i < 2; i++)
                    U.push_back(1);
                A -= (sz >= 3 ? D[sz - 3] : 0);
                sz -= 2;
            }
            else
            {
                lst = 0;
                for (int i = 0; i < 3; i++)
                    U.push_back(0);
                sz -= 3;
            }
        }
        else
        {
            if (A >= (sz >= 2 ? D[sz - 2] : 0))
            {
                lst = 1;
                for (int i = 0; i < 3; i++)
                    U.push_back(1);
                A -= (sz >= 2 ? D[sz - 2] : 0);
                sz -= 3;
            }
            else
            {
                for (int i = 0; i < 2; i++)
                    U.push_back(0);
                sz -= 2;
            }
        }
    }
    return {U, V};
}

pair<vector<int>, vector<int>> Anna(long long A)
{
    --A;
    for (int i = 1; i <= MAX; i++)
    {
        if (A >= 2 * D[i - 1])
            A -= 2 * D[i - 1];
        else
            return Asolve(i, A);
    }
    cerr << A << endl;
    assert(false);
}

Bruno

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

namespace
{
    const int MAX = 140;
    bool inited = false;
    vector<long long> D(MAX + 1);
    void init()
    {
        if (inited)
            return;
        inited = true;
        D[0] = 1, D[1] = 1, D[2] = 2;
        for (int i = 3; i < MAX; i++)
            D[i] = D[i - 2] + D[i - 3] + 1;
    }
}

long long bsolve(vector<int> u)
{
    int rem = u.size() / 2, state = 0, ulimit = 1, ucount = 1, dlimit = -1, dcount = 1;
    long long ret = 0, uplus = D[rem - 1], dplus = 0;
    for (int v : u)
    {
        state += v * 2 - 1;
        if (state == ulimit)
        {
            ret += uplus, rem -= ucount;
            ulimit = state + 2, ucount = 2;
            uplus = (rem >= 3 ? D[rem - 3] : 0) + 1, dplus = 1;
            dlimit = state - 2, dcount = 3;
        }
        else if (state == dlimit)
        {
            ret += dplus, rem -= dcount;
            ulimit = state + 2, ucount = 3;
            uplus = (rem >= 2 ? D[rem - 2] : 0) + 1, dplus = 1;
            dlimit = state - 2, dcount = 2;
        }
    }
    return ret;
}

long long Bruno(vector<int> u)
{
    init();
    long long ans = 1;
    for (int i = 1; i < (int)u.size() / 2; i++)
        ans += 2 * D[i - 1];
    return ans + bsolve(u);
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 60 / 60