Submission #483178

#	Time	Username	Problem	Language	Result	Execution time	Memory
483178		daongocha	Lamps (JOI19_lamps)	C++14	100 / 100	173 ms	54292 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;
int dp[MAXN][13];
int cost[13][13];
int turn[2][13];

signed main() {
    int n; cin >> n;
    string s, t;
    cin >> s >> t;
    s = "0" + s; t = "0" + t;
    for (char &c: s) c -= '0';
    for (char &c: t) c -= '0';
    memset(dp, 0x3f, sizeof dp);
    

    
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 13; j++) {
            int v = i;
            if (j == 0) v = 1;
            else if (j == 1) v = 0;
            else if (j == 2) v = 1;
            else if (j == 3) v = 0;
            else if (j == 4) v = 0;
            else if (j == 5) v = 1;
            else if (j == 6) v = 0;
            else if (j == 7) v = 1;
            else if (j == 9) v = 0;
            else if (j == 10) v = 1;
            else if (j == 11) v ^= 1;
            turn[i][j] = v;
        }

    // i = 0 => 01
    // i = 1 => 10
    // i = 2 => 02
    // i = 3 => 20
    // i = 4 => 12
    // i = 5 => 21
    // i = 6 => 00
    // i = 7 => 11
    // i = 8 => 22
    // i = 9 => 0
    // i = 10 => 1
    // i = 11 => 2
    // i = 12 => none

    for (int i = 0; i < 12; i++)
        for (int j = 0; j < 12; j++) {
            if (i == j) continue;
            bool i0 = (i == 0 || i == 1 || i == 2 || i == 3 || i == 6 || i == 9);
            bool i1 = (i == 0 || i == 1 || i == 4 || i == 5 || i == 7 || i == 10);
            bool i2 = (i == 2 || i == 3 || i == 4 || i == 5 || i == 8 || i == 11);
            
            bool j0 = (j == 0 || j == 1 || j == 2 || j == 3 || j == 6 || j == 9);
            bool j1 = (j == 0 || j == 1 || j == 4 || j == 5 || j == 7 || j == 10);
            bool j2 = (j == 2 || j == 3 || j == 4 || j == 5 || j == 8 || j == 11);
            
            cost[i][j] = 2;
            if (i0 && j0) cost[i][j] = 1;
            if (i1 && j1) cost[i][j] = 1;
            if (i2 && j2) cost[i][j] = 1;
            
            if (i0 && j == 9) cost[i][j] = 0;
            else if (i1 && j == 10) cost[i][j] = 0;
            else if (i2 && j == 11) cost[i][j] = 0;
        }
    
    for (int j = 0; j < 13; j++) {
        if (j >= 12) cost[12][j] = 0;
        else if (j >= 9) cost[12][j] = 1;
        else cost[12][j] = 2;
    }
    
    dp[0][12] = 0;
    
    s += (char)0; t += (char)0;
    
    
    int mn = 1e9;
    for (int i = 1; i <= n + 1; i++) {
        for (int msk = 0; msk < 13; msk++) {
            char c = s[i];
            c = turn[c][msk];
            
            dp[i][msk] = 1e9;
            
            if (c == t[i]) {
                for (int pre = 0; pre < 13; pre++) 
                    dp[i][msk] = min(dp[i][msk], dp[i - 1][pre] + cost[pre][msk]);
            }
        }
    }

    cout << dp[n + 1][12];
}  

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:89:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |             c = turn[c][msk];
      |                      ^
lamp.cpp:85:9: warning: unused variable 'mn' [-Wunused-variable]
   85 |     int mn = 1e9;
      |         ^~

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