Submission #643188

#	Time	Username	Problem	Language	Result	Execution time	Memory
643188		cologne	Broken Device 2 (JOI22_device2)	C++17	80 / 100	104 ms	3680 KiB

Anna

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

int Declare()
{
    return 180;
}

pair<vector<int>, vector<int>> Anna(long long A)
{
    vector<int> U, V;
    for(int i=59; i>=0; --i)
        for(int j=0; j<3; j++)
            U.push_back((A>>i)&1);
    for(int i=0; i<90; i++)
        V.push_back(0), V.push_back(1);
    return {U, V};
}

Bruno

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

enum State
{
    P1_0_1_or_N_11_1_or_P1_00_0,
    P1_N_1_or_N_11_0_or_P1_0_0,
    N_11_1_or_N_1_0,
    N_1_1_or_N_N_0,
    N_0_0_or_N_N_1,
    N_00_0_or_N_0_1,
    P0_N_0_or_N_00_1_or_P0_1_1,
    P0_1_0_or_N_00_0_or_P0_11_1,
};

pair<int, State> t0(State A)
{
    switch (A)
    {
    case P1_0_1_or_N_11_1_or_P1_00_0:
        return {1, P0_N_0_or_N_00_1_or_P0_1_1};
    case P1_N_1_or_N_11_0_or_P1_0_0:
        return {-1, P1_0_1_or_N_11_1_or_P1_00_0};
    case N_11_1_or_N_1_0:
        return {-1, N_1_1_or_N_N_0};
    case N_1_1_or_N_N_0:
        return {-1, N_0_0_or_N_N_1};
    case N_0_0_or_N_N_1:
        return {-1, N_00_0_or_N_0_1};
    case N_00_0_or_N_0_1:
        return {-1, P0_N_0_or_N_00_1_or_P0_1_1};
    case P0_N_0_or_N_00_1_or_P0_1_1:
        return {0, N_0_0_or_N_N_1};
    case P0_1_0_or_N_00_0_or_P0_11_1:
        return {-1, P0_N_0_or_N_00_1_or_P0_1_1};
    }
    assert(false);
}

pair<int, State> t1(State A)
{
    switch (A)
    {
    case P1_0_1_or_N_11_1_or_P1_00_0:
        return {-1, P1_N_1_or_N_11_0_or_P1_0_0};
    case P1_N_1_or_N_11_0_or_P1_0_0:
        return {1, N_1_1_or_N_N_0};
    case N_11_1_or_N_1_0:
        return {-1, P1_N_1_or_N_11_0_or_P1_0_0};
    case N_1_1_or_N_N_0:
        return {-1, N_11_1_or_N_1_0};
    case N_0_0_or_N_N_1:
        return {-1, N_1_1_or_N_N_0};
    case N_00_0_or_N_0_1:
        return {-1, N_0_0_or_N_N_1};
    case P0_N_0_or_N_00_1_or_P0_1_1:
        return {-1, P0_1_0_or_N_00_0_or_P0_11_1};
    case P0_1_0_or_N_00_0_or_P0_11_1:
        return {0, P1_N_1_or_N_11_0_or_P1_0_0};
    }
    assert(false);
}

int final(State A)
{
    switch (A)
    {
    case P1_0_1_or_N_11_1_or_P1_00_0:
        return 1;
    case P1_N_1_or_N_11_0_or_P1_0_0:
        return 1;
    case N_11_1_or_N_1_0:
        assert(false);
        return -1;
    case N_1_1_or_N_N_0:
        return -1;
    case N_0_0_or_N_N_1:
        return -1;
    case N_00_0_or_N_0_1:
        assert(false);
        return -1;
    case P0_N_0_or_N_00_1_or_P0_1_1:
        return 0;
    case P0_1_0_or_N_00_0_or_P0_11_1:
        return 0;
    }
    assert(false);
}

long long Bruno(vector<int> u)
{
    long long ret = 0;
    State cur = N_1_1_or_N_N_0;
    for (int v : u)
    {
        auto [x, y] = v ? t1(cur) : t0(cur);
        if (x != -1)
            ret = ret * 2 + x;
        cur = y;
    }

    int x = final(cur);
    if (x != -1)
        ret = ret * 2 + x;
    return ret;
}

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