oj.uz

Submission #1092483

# Submission time Handle Problem Language Result Execution time Memory
1092483 2024-09-24T08:05:13 Z LOLOLO Lamps (JOI19_lamps) C++14
4 / 100
 14 ms 16204 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e6 + 100;
int f[N][3];
string a, b;

char get(int x, int y) {
    if (y == 1)
        return '0';

    if (y == 2)
        return '1';

    return a[x];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("LIGHTS.inp", "r", stdin);
    //freopen("LIGHTS.out", "w", stdout);

    mem(f, 0x3f);
    int n;
    cin >> n;
    cin >> a >> b;

    f[0][0] = (a[0] != b[0]);
    f[0][1] = (b[0] != '0') + 1;
    f[0][2] = (b[0] != '1') + 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                char s1 = get(i - 1, j), s2 = get(i, k);
                int d1 = s1 != b[i - 1], d2 = s2 != b[i];
                f[i][k] = min(f[i][k], f[i - 1][j] + (d1 != d2 && d2 == 1) + (k != j && k));
            }
        }
    }

    cout << min({f[n - 1][0], f[n - 1][1], f[n - 1][2]}) << '\n';
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 5 ms 11972 KB Output is correct
5 Correct 5 ms 12120 KB Output is correct
6 Correct 5 ms 12120 KB Output is correct
7 Correct 5 ms 12196 KB Output is correct
8 Correct 4 ms 12124 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12108 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 4 ms 12124 KB Output is correct
14 Incorrect 4 ms 12124 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 5 ms 11972 KB Output is correct
5 Correct 5 ms 12120 KB Output is correct
6 Correct 5 ms 12120 KB Output is correct
7 Correct 5 ms 12196 KB Output is correct
8 Correct 4 ms 12124 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12108 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 4 ms 12124 KB Output is correct
14 Incorrect 4 ms 12124 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 6 ms 12120 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12120 KB Output is correct
7 Correct 13 ms 16144 KB Output is correct
8 Correct 13 ms 16204 KB Output is correct
9 Correct 13 ms 16120 KB Output is correct
10 Correct 13 ms 16116 KB Output is correct
11 Correct 13 ms 16120 KB Output is correct
12 Correct 13 ms 16120 KB Output is correct
13 Correct 12 ms 16120 KB Output is correct
14 Correct 14 ms 16120 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 5 ms 11972 KB Output is correct
5 Correct 5 ms 12120 KB Output is correct
6 Correct 5 ms 12120 KB Output is correct
7 Correct 5 ms 12196 KB Output is correct
8 Correct 4 ms 12124 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12108 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 4 ms 12124 KB Output is correct
14 Incorrect 4 ms 12124 KB Output isn't correct
15 Halted 0 ms 0 KB -