oj.uz

Submission #483176

# Submission time Handle Problem Language Result Execution time Memory
483176 2021-10-28T03:43:16 Z baokhue232005 Lamps (JOI19_lamps) C++14
0 / 100
 22 ms 51148 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;
int dp[MAXN][13];
int cost[13][13];
// 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

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;
        }
    
    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[j][12] = cost[12][j] = 0;
        else if (j >= 9) cost[j][12] = cost[12][j] = 1;
        else cost[j][12] = cost[12][j] = 2;
    }
    
    dp[0][0] = 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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 51148 KB Output is correct
2 Incorrect 19 ms 51064 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 51148 KB Output is correct
2 Incorrect 19 ms 51064 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 51092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 51148 KB Output is correct
2 Incorrect 19 ms 51064 KB Output isn't correct
3 Halted 0 ms 0 KB -