Submission #921958

#	Time	Username	Problem	Language	Result	Execution time	Memory
921958		boris_mihov	Lamps (JOI19_lamps)	C++17	100 / 100	742 ms	192352 KiB

lamp

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF  = 1e9;

int n;
char a[MAXN];
char b[MAXN];
int add[16][16];
int rem[16][16];
int getBit[2][16];
int dp[MAXN][16];
bool bl[MAXN][16];

const std::vector <int> statePerms[] = 
{
    {},
    {1},
    {2},
    {3},
    {1, 2},
    {1, 3},
    {2, 3},
    {2, 1},
    {3, 1},
    {3, 2},
    {1, 2, 3},
    {1, 3, 2},
    {2, 1, 3},
    {2, 3, 1},
    {3, 1, 2},
    {3, 2, 1}
};

int f(int idx, int state)
{
    if (idx == n + 1)
    {
        return 0;
    }

    if (bl[idx][state])
    {
        return dp[idx][state];
    }

    bl[idx][state] = true;
    dp[idx][state] = f(idx + 1, state) + (getBit[a[idx] - '0'][state] != b[idx] - '0');

    for (int newMask = 0 ; newMask < 16 ; ++newMask)
    {
        if (add[state][newMask] == INF || getBit[a[idx] - '0'][newMask] != b[idx] - '0')
        {
            continue;
        }

        dp[idx][state] = std::min(dp[idx][state], add[state][newMask] + f(idx + 1, newMask));
    }

    for (int newMask = 0 ; newMask < 16 ; ++newMask)
    {
        if (rem[state][newMask] != INF)
        {
            dp[idx][state] = std::min(dp[idx][state], (getBit[a[idx] - '0'][state] != b[idx] - '0') + f(idx + 1, newMask));
        }
    }

    return dp[idx][state];
}

bool contains(int idxOne, int idxTwo)
{
    int ptrA = 0;
    int ptrB = 0;
    while (ptrA < statePerms[idxOne].size())
    {
        if (ptrB == statePerms[idxTwo].size())
        {
            return false;
        }

        if (statePerms[idxOne][ptrA] == statePerms[idxTwo][ptrB])
        {
            ptrA++;
        }

        ptrB++;
    }

    return true;
}

int getNewBit(int myBit, int myOp)
{
    if (myOp == 1)
    {
        return 0;
    }

    if (myOp == 2)
    {
        return 1;
    }

    return myBit ^ 1;
}

void solve()
{
    for (int bit = 0 ; bit < 2 ; ++bit)
    {
        for (int mask = 0 ; mask < 16 ; ++mask)
        {
            getBit[bit][mask] = bit;
            for (const int &op : statePerms[mask])
            {
                getBit[bit][mask] = getNewBit(getBit[bit][mask], op);
            }
        }
    }

    for (int i = 0 ; i < 16 ; ++i)
    {
        for (int j = 0 ; j < 16 ; ++j)
        {
            add[i][j] = INF;
            rem[i][j] = INF;
        }
    }

    for (int maskOne = 0 ; maskOne < 16 ; ++maskOne)
    {
        for (int maskTwo = 0 ; maskTwo < 16 ; ++maskTwo)
        {
            if (maskOne == maskTwo || !contains(maskOne, maskTwo))
            {
                continue;
            }
            
            add[maskOne][maskTwo] = statePerms[maskTwo].size() - statePerms[maskOne].size();
            rem[maskTwo][maskOne] = 0;
        }
    }

    std::cout << f(1, 0) << '\n';
}

void input()
{
    std::cin >> n;
    std::cin >> a + 1;
    std::cin >> b + 1;
}   

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'bool contains(int, int)':
lamp.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     while (ptrA < statePerms[idxOne].size())
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         if (ptrB == statePerms[idxTwo].size())
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp: In function 'void input()':
lamp.cpp:156:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  156 |     std::cin >> a + 1;
      |                 ~~^~~
lamp.cpp:157:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  157 |     std::cin >> b + 1;
      |                 ~~^~~

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