Submission #643439

#	Time	Username	Problem	Language	Result	Execution time	Memory
643439		cologne	Broken Device 2 (JOI22_device2)	C++17	96 / 100	64 ms	2908 KiB

Anna

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

namespace
{
    const int MAX = 141;
    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;
    for (int i = 0; i < sz; i++)
        V.push_back(i & 1);

    int lst = 0;

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

    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 = 2; i <= MAX; i++)
    {
        if (A >= 2 * D[i - 2])
            A -= 2 * D[i - 2];
        else
            return Asolve(i, A);
    }
    assert(false);
}

Bruno

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

namespace
{
    const int MAX = 150;
    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 N = u.size() / 2, rem = N, prv = -1;
    long long ret = -1;

    int state = 1, ulimit = 3, ucount = 2;
    long long uplus = D[rem - 2];
    int dlimit = -3, dcount = 2;
    for (int v : u)
    {
        state += v * 4 - 2;
        if (state == ulimit)
        {
            ret += uplus + 1;
            rem -= ucount;
            ulimit = state + 4;
            ucount = 2;
            uplus = rem >= 3 ? D[rem - 3] : 0;
            dlimit = state - 4;
            dcount = 3;
        }
        else if (state == dlimit)
        {
            ret += 1;
            rem -= dcount;
            ulimit = state + 4;
            ucount = 3;
            uplus = rem >= 2 ? D[rem - 2] : 0;
            dlimit = state - 4;
            dcount = 2;
        }
    }

    return ret;
}

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

Compilation message (stderr)

Bruno.cpp: In function 'long long int bsolve(std::vector<int>)':
Bruno.cpp:23:36: warning: unused variable 'prv' [-Wunused-variable]
   23 |     int N = u.size() / 2, rem = N, prv = -1;
      |                                    ^~~

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