oj.uz

Submission #156997

# Submission time Handle Problem Language Result Execution time Memory
156997 2019-10-09T01:46:52 Z atoiz Lamps (JOI19_lamps) C++14
4 / 100
 30 ms 4528 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <climits>
#include <random>
#include <chrono>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <ios>
#include <iomanip>

using namespace std;

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)
#define SZ(a) ((int) a.size())
#define ALL(a) begin(a), end(a)

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INF = 1e9;
int N;
string A, B;
int F[2][2][3];
void upd(int &a, int b) { if (a > b) a = b; }

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> A >> B;
    FOR(i, 0, 1) FOR(j, 0, 1) FOR(k, 0, 2) F[i][j][k] = INF;
    F[0][0][0] = 1;
    F[0][1][0] = (A[0] != B[0]);
    FOR(i, 0, N - 2) {
        int id = i & 1;
        // FOR(j, 0, 1) FOR(k, 0, 2) cerr << F[id][j][k] << ' '; cerr << endl;
        FOR(j, 0, 1) FOR(k, 0, 2) F[id ^ 1][j][k] = INF;

        if (B[i] == B[i + 1]) {
            FOR(k, 0, 2) upd(F[id ^ 1][0][k], F[id][0][k]);
        } else {
            upd(F[id ^ 1][0][1], F[id][0][0] + 1);
            upd(F[id ^ 1][0][2], F[id][0][1]);
            upd(F[id ^ 1][0][1], F[id][0][2] + 1);
        }
        FOR(k, 0, 2) upd(F[id ^ 1][0][0], F[id][1][k] + 1);

        if ((A[i] != B[i]) == (A[i + 1] != B[i + 1])) {
            FOR(k, 0, 2) upd(F[id ^ 1][1][k], F[id][1][k]);
        } else {
            upd(F[id ^ 1][1][1], F[id][1][0] + 1);
            upd(F[id ^ 1][1][2], F[id][1][1]);
            upd(F[id ^ 1][1][1], F[id][1][2] + 1);
        }
        FOR(k, 0, 2) upd(F[id ^ 1][1][0], F[id][0][k] + (A[i + 1] != B[i + 1]));
    }

    int ans = INF;
    FOR(j, 0, 1) FOR(k, 0, 2) upd(ans, F[(N - 1) & 1][j][k]);
    cout << ans << endl;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 416 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 252 KB Output is correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 416 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 252 KB Output is correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 30 ms 4424 KB Output is correct
8 Correct 29 ms 4424 KB Output is correct
9 Correct 28 ms 4496 KB Output is correct
10 Correct 27 ms 4428 KB Output is correct
11 Correct 27 ms 4428 KB Output is correct
12 Correct 28 ms 4480 KB Output is correct
13 Correct 28 ms 4468 KB Output is correct
14 Correct 28 ms 4528 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 416 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 252 KB Output is correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -