Submission #230169

#	Time	Username	Problem	Language	Result	Execution time	Memory
230169		DS007	Lamps (JOI19_lamps)	C++14	4 / 100	74 ms	7304 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define find(l, r) (1 + (r - l) / 2)

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 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_;
    for (int p = lp; p < n_; p++) {
        if (a_[p] == b_[p])
            return find(lp, p) + solve(p + 1);
        if (a_[p] == '2')
            last = n_;
        else if (last == n_)
            last = p;
        else if (b_[p] != b_[lp] && last < p - 1)
            return find(lp, last) + 1 + solve(toggle(last));
    }

    return last == lp ? 1 : find(lp, n_);
}

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

    for (int i = 0; i < n; n_++) {
        set<char> s;
        int temp = i;

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

        b_ += b[i];
        a_ += s.size() == 2 ? '2' : *s.begin();
        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:55: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