Submission #1013844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013844		toan2602	Lamps (JOI19_lamps)	C++14	4 / 100	14 ms	19976 KiB

lamp

#include<bits/stdc++.h>

using namespace std;

int n, dp[1000005], p0[1000005], p1[1000005], dif[1000005];
string a, b;
void solve() {
    cin >> n >> a >> b;
    a = ' ' + a;
    b = ' ' + b;
    a[0] = '#';
    b[0] = '&';
    int cnt =0, res = 0;
    for (int i = 1; i < b.size(); i++) {
        if(b[i] == '0') p0[i] = (b[i-1] == '0' ? p0[i-1] + 1 : 1);
        else p1[i] = (b[i-1] == '1' ? p1[i-1] + 1 : 1);
        if(a[i] != b[i]) dif[i] = (a[i-1] != b[i-1] ? dif[i-1] : i-1);
    }
    for (int i = 1; i < a.size(); i++) {
        if(a[i] == b[i]) dp[i] = dp[i-1];
        else dp[i] = min(dp[dif[i]] + 1, dp[i-1]+1);
        if(b[i] == '0') dp[i] = min(dp[i-p0[i]] + 1, dp[i]);
        else dp[i] = min(dp[i-p1[i]]+1, dp[i]);
    }
    cout << dp[n];
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
}

Compilation message (stderr)

lamp.cpp: In function 'void solve()':
lamp.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 1; i < b.size(); i++) {
      |                     ~~^~~~~~~~~~
lamp.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 1; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
lamp.cpp:13:9: warning: unused variable 'cnt' [-Wunused-variable]
   13 |     int cnt =0, res = 0;
      |         ^~~
lamp.cpp:13:17: warning: unused variable 'res' [-Wunused-variable]
   13 |     int cnt =0, res = 0;
      |                 ^~~

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