Submission #688476

#	Time	Username	Problem	Language	Result	Execution time	Memory
688476		AJR07	Lamps (JOI19_lamps)	C++17	100 / 100	156 ms	161240 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define DBGRUN(stmt) stmt
#define DBG1(x) cout << #x << ": " << (x) << endl
#define DBG2(x, y) cout << #x << ": " << (x) << ", " << #y << ": " << (y) << endl
#define DBG3(x, y, z) cout << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << endl
#define DBG4(w, x, y, z) cout << #w << ": " << (w) << ", " << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << endl
#define DBG_ARR(a, e) cout << #a << ": "; for (int i = 0; i < e; i++) cout << a[i] << ' '; cout << endl
#define DBG_ARR2D(a, s1, e1, s2, e2) cout << #a << ": " << endl; for (int i = s1; i < e1; i++) { for (int j = s2; j < e2; j++) cout << a[i][j] << ' '; cout << '\n'; }cout << endl
#define DBG_VEC(v) cout << #v << ": "; for (auto i : v) cout << i << ' '; cout << endl
#define DBG_HERE cout << "reached line: " << __LINE__ << endl
#else
#define DBGRUN(stmt)
#define DBG1(x)
#define DBG2(x, y)
#define DBG3(x, y, z)
#define DBG4(w, x, y, z)
#define DBG_ARR(a, e)
#define DBG_ARR2D(a, s1, e1, s2, e2)
#define DBG_VEC(v)
#define DBG_HERE
#endif
#define int long long
#define f first
#define s second
#define pii pair<int, int>
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a)) 
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define FORR(a, b, c) for (int(a) = (b); (a) >= (c); --(a))
#define ALLV(v) v.begin(), v.end() 
#define ALLA(arr, sz) arr, arr + sz
#define SORT(v) sort(ALL(v)) 
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz)) 
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
template <typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B>& a) { out << "(" << a.first << ", " << a.second << ")"; return out; }
template<typename ...Ts, size_t ...Is> ostream& println_tuple_impl(ostream& os, tuple<Ts...> tuple, index_sequence<Is...>) { static_assert(sizeof...(Is) == sizeof...(Ts), "Indices must have same number of elements as tuple types!"); static_assert(sizeof...(Ts) > 0, "Cannot insert empty tuple into stream."); auto last = sizeof...(Ts) - 1; os << "("; return ((os << get<Is>(tuple) << (Is != last ? ", " : ")\n")), ...); }
template<typename ...Ts> ostream& operator<<(ostream& os, const tuple<Ts...>& tuple) { return println_tuple_impl(os, tuple, index_sequence_for<Ts...>{}); }

int N, memo[1000010][2][2][2];
vector<bool> AA, BB;
string A, B;

int dp(int idx, bool toggleOpen, bool rangeSetOpen, bool toggleFirst) {
    if (memo[idx][toggleOpen][rangeSetOpen][toggleFirst] != -1)
        return memo[idx][toggleOpen][rangeSetOpen][toggleFirst];
    if (idx == N) return 0;

    int res = 1e18;
    if (!toggleOpen && !rangeSetOpen) {
        // don't do any operations 
        if (AA[idx] == BB[idx]) res = min(res, dp(idx + 1, false, false, false));
        // do toggle
        if (AA[idx] == !BB[idx]) res = min(res, dp(idx + 1, true, false, true) + 1);
        // do range_set
        res = min(res, dp(idx + 1, false, true, false) + 1);
        // do toggle and range_set, but in different orders
        res = min(res, dp(idx + 1, true, true, true) + 2);
        res = min(res, dp(idx + 1, true, true, false) + 2);
    }

    if (!toggleOpen && rangeSetOpen) {
        // close rangeSetOpen
        if (AA[idx] == BB[idx]) res = min(res, dp(idx + 1, false, false, false));
        // do toggle & close rangeSetOpen
        if (AA[idx] == !BB[idx]) res = min(res, dp(idx + 1, true, false, true) + 1);
        // do rangSetOpen as it is
        if (BB[idx] == BB[idx - 1]) res = min(res, dp(idx + 1, false, true, false));
        // do toggle and range_set
        if (!BB[idx - 1] == BB[idx]) res = min(res, dp(idx + 1, true, true, false) + 1);
    }

    if (toggleOpen && !rangeSetOpen) {
        // close toggleOpen
        if (AA[idx] == BB[idx]) res = min(res, dp(idx + 1, false, false, false));
        // do rangeSetOpen & close toggle
        res = min(res, dp(idx + 1, false, true, false) + 1);
        // do toggle as it is
        if (AA[idx] == !BB[idx]) res = min(res, dp(idx + 1, true, false, true));
        // do toggle and range_set
        res = min(res, dp(idx + 1, true, true, true) + 1);
    }

    if (toggleOpen && rangeSetOpen) {
        // do it as it is
        if (BB[idx - 1] == BB[idx]) res = min(res, dp(idx + 1, true, true, true));
        // close rangeSetOpen
        if (AA[idx] == !BB[idx]) res = min(res, dp(idx + 1, true, false, true));
        // close toggle
        if (BB[idx] == !BB[idx - 1]) res = min(res, dp(idx + 1, false, true, false));
        // close both
        if (AA[idx] == BB[idx]) res = min(res, dp(idx + 1, false, false, false));
    }

    memo[idx][toggleOpen][rangeSetOpen][toggleFirst] = res;
    return res;
}

int32_t main() {
    memset(memo, -1, sizeof memo);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    cin >> A >> B;
    for (auto i : A) AA.push_back(i - '0');
    for (auto i : B) BB.push_back(i - '0');

    cout << dp(0, false, false, false);
}

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