Submission #444469

#	Time	Username	Problem	Language	Result	Execution time	Memory
444469		blue	Lamps (JOI19_lamps)	C++17	100 / 100	725 ms	6292 KiB

lamp

#include <iostream>
#include <vector>
using namespace std;

/*
States:

0       nothing
1       on
2       off
3       toggle
4       on + off
5       on + toggle
6       off + on
7       off + toggle
8       toggle + on
9       toggle + off
*/

const int off = 0;
const int on = 1;
const int toggle = 2;

string s[3] = {"OFF", "ON", "TOGGLE"};

int op_res(int a, int b)
{
    if(b == off) return 0;
    else if(b == on) return 1;
    else return !a;
}

vector<int> ops[10];

int ops_res(int a, int b)
{
    for(int x: ops[b]) a = op_res(a, x);
    return a;
}

int cost(int ops1, int ops2)
{
    int ans = ops[ops2].size();

    int reducevalue = 0;
    if(ops[ops1] == ops[ops2]) reducevalue = ops[ops2].size();
    else
    {
        for(int x: ops[ops1])
            for(int y: ops[ops2])
                if(x == y)
                    reducevalue = 1;
    }

    return ans - reducevalue;
}

const long long INF = 1'000'000'000LL;

long long* dp1;
long long* dp2;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ops[0] = vector<int>{};
    ops[1] = vector<int>{off};
    ops[2] = vector<int>{on};
    ops[3] = vector<int>{toggle};
    ops[4] = vector<int>{off, on};
    ops[5] = vector<int>{off, toggle};
    ops[6] = vector<int>{on, off};
    ops[7] = vector<int>{on, toggle};
    ops[8] = vector<int>{toggle, off};
    ops[9] = vector<int>{toggle, on};

    // for(int i = 0; i <= 9; i++)
    //     for(int j = 0; j <= 9; j++)
    //     {
    //         for(int x: ops[i]) cerr << s[x] << ' ';
    //         cerr << "-> ";
    //         for(int y: ops[j]) cerr << s[y] << ' ';
    //         cerr << ": ";
    //         cerr << cost(i, j) << '\n';
    //     }

    int N;
    cin >> N;

    string A;
    cin >> A;
    A = " " + A;

    string B;
    cin >> B;

    B = " " + B;

    dp1 = new long long[10];
    dp2 = new long long[10];


    dp2[0] = 0;
    for(int o = 1; o < 10; o++) dp2[o] = INF;

    for(int i = 1; i <= N; i++)
    {
        swap(dp1, dp2);
        for(int o2 = 0; o2 < 10; o2++)
        {
            if(ops_res(A[i] - '0', o2) != (B[i] - '0'))
            {
                dp2[o2] = INF;
            }
            else
            {
                dp2[o2] = INF;
                for(int o1 = 0; o1 < 10; o1++)
                {
                    dp2[o2] = min(dp2[o2], dp1[o1] + cost(o1, o2));
                }
            }
        }
    }

    long long ans = INF;
    for(int o = 0; o < 10; o++)
        ans = min(ans, dp2[o]);

    cout << ans << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49