# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
245762 | pavel | Lamps (JOI19_lamps) | C++14 | 26 ms | 8064 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1000006;
int n;
char a[MAXN], b[MAXN];
int chg[MAXN];
int main(){
scanf("%d", &n);
scanf("%s", a);
scanf("%s", b);
for(int i=1;i<n;++i){
chg[i] = chg[i-1];
if(b[i] != b[i-1]) chg[i]++;
}
int l = 0, r = n;
int sol = MAXN;
int flips = 0;
while(l != r){
if(flips%2 == 0){
while(a[l]==b[l] && l<r) l++;
while(a[r-1]==b[r-1] && l<r) r--;
}else{
while(a[l]!=b[l] && l<r) l++;
while(a[r-1]!=b[r-1] && l<r) r--;
}
if(l == r){
sol = min(sol, flips);
break;
}
int cost = (chg[r-1] - chg[l] + 1) / 2;
sol = min(sol, flips+1+cost);
flips++;
}
printf("%d\n", sol);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |