Submission #230174

#	Time	Username	Problem	Language	Result	Execution time	Memory
230174		DS007	Lamps (JOI19_lamps)	C++14	4 / 100	29 ms	5812 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, n_;
string a, b, a_, b_;

int toggle(int p) {
    while (p != n_ && a_[p] != 2 && a_[p] != b_[p])
        p++;
    return p;
}

int find(int l, int r) {
    while (l != r && a_[l] == b_[l])
        l++;

    r--;
    while (l <= r && a_[r] == b_[r])
        r--;

    if (l > r)
        return 0;

    int change = 0;
    for (int i = l; i <= r; i++) {
        if (b_[i] != b_[l] && b_[i] != b_[i - 1])
            change++;
    }
    return change + 1;
}

int solve(int lp) {
    while (lp != n_ && a_[lp] == b_[lp])
        lp++;
    if (lp == n_)
        return 0;
    if (lp == n_ - 1)
        return 1;

    int last = n_, change = 0;
    for (int p = lp; p < n_; p++) {
        if (b_[p] != b_[lp] && b_[p] == a_[p] && (p == n - 1 || b_[p] != b_[p + 1]))
            return 1 + change + solve(p);
        if (b[p] != b[lp] && b[p] != b[p - 1])
            change++;
        if (a_[p] == b_[p])
            last = n_;
        else if (last == n_)
            last = p;
        if (last < p - 1 && b_[p] != b_[lp])
            return find(lp, last) + 1 + solve(toggle(last));
    }

    return last == lp ? 1 : 1 + change;
}

int solveTestCase(int test) {
    cin >> n >> a >> b;

    for (int i = 0; i < n; n_++) {
        int temp = i;

        while (temp != n && b[temp] == b[i] && a[temp] == a[i])
            temp++;

        b_ += b[i];
        a_ += a[i];
        i = temp;
    }

    //cout << a_ << endl << b_ << endl;
    cout << solve(0);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase(i);
}

Compilation message (stderr)

lamp.cpp: In function 'long long int solveTestCase(long long int)':
lamp.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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