Submission #947866

#	Time	Username	Problem	Language	Result	Execution time	Memory
947866		danikoynov	Lamps (JOI19_lamps)	C++14	100 / 100	65 ms	51320 KiB

lamp

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e6 + 10;

int n;
string a, b;

/**
0 - no operations
1 - set 0 = 0
2 - set 1 = 1
3 - toggle = switch
4 - set 0 toggle = 1
5 - set 1 toggle = 0
*/

const int maxmask = 6;
int path[maxmask][maxmask], to[2][maxmask];
void precompute_masks()
{
    to[0][0] = 0;
    to[1][0] = 1;

    to[0][1] = 0;
    to[1][1] = 0;

    to[0][2] = 1;
    to[1][2] = 1;

    to[0][3] = 1;
    to[1][3] = 0;

    to[0][4] = 1;
    to[1][4] = 1;

    to[0][5] = 0;
    to[1][5] = 0;

    path[0][0] = 0;
    path[0][1] = 1;
    path[0][2] = 1;
    path[0][3] = 1;
    path[0][4] = 2;
    path[0][5] = 2;

    path[1][0] = 0;
    path[1][1] = 0;
    path[1][2] = 1;
    path[1][3] = 1;
    path[1][4] = 1;
    path[1][5] = 2;

    path[2][0] = 0;
    path[2][1] = 1;
    path[2][2] = 0;
    path[2][3] = 1;
    path[2][4] = 2;
    path[2][5] = 1;

    path[3][0] = 0;
    path[3][1] = 1;
    path[3][2] = 1;
    path[3][3] = 0;
    path[3][4] = 1;
    path[3][5] = 1;

    path[4][0] = 0;
    path[4][1] = 0;
    path[4][2] = 1;
    path[4][3] = 0;
    path[4][4] = 0;
    path[4][5] = 1;

    path[5][0] = 0;
    path[5][1] = 1;
    path[5][2] = 0;
    path[5][3] = 0;
    path[5][4] = 1;
    path[5][5] = 0;
}

int dp[maxn][maxmask], f[maxn][maxmask];
void solve()
{
    cin >> n >> a >> b;

    precompute_masks();
    a = "#" + a;
    b = "#" + b;

    for (int i = 0; i <= n; i ++)
    {
        for (int mask = 0; mask < maxmask; mask ++)
            dp[i][mask] = 1e9, f[i][mask] = -1;
    }

    dp[0][0] = 0;
    for (int i = 1; i <= n; i ++)
    {
        for (int mask = 0; mask < maxmask; mask ++)
        {
            if (to[a[i] - '0'][mask] != b[i] - '0')
                continue;

            for (int from = 0; from < maxmask; from ++)
            {
                int val = dp[i - 1][from] + path[from][mask];
                if (val < dp[i][mask])
                {
                    dp[i][mask] = val;
                    f[i][mask] = from;
                }
            }
        }
        /**cout << "--------------------" << endl;
        for (int mask = 0; mask < maxmask; mask ++)
        {
            cout << dp[i][mask] << " ";
        }
        cout << endl;

                for (int mask = 0; mask < maxmask; mask ++)
        {
            cout << f[i][mask] << " ";
        }
        cout << endl;*/
    }

    int ans = 1e9;
    for (int mask = 0; mask < maxmask; mask ++)
        ans = min(ans, dp[n][mask]);

    cout << ans << endl;

}

int main()
{
    speed();
    int t = 1;
    ///cin >> t;
    while(t --)
        solve();
    return 0;
}

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