Submission #769106

#TimeUsernameProblemLanguageResultExecution timeMemory
769106Mohammad_ParsaLamps (JOI19_lamps)C++17
4 / 100
27 ms18944 KiB
/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=1e6+7;
int n,nxt[N],bad[N],s[N];
string a,b,c;

int solve(string a,string b){
	int ans=0;
	nxt[n-1]=n-1;
	for(int i=n-2;i>=0;i--){
		nxt[i]=i;
		if(b[i]==b[i+1])nxt[i]=nxt[i+1];
	}
	for(int i=0;i<n;i++){
		if(a[i]!=b[i])s[i]=1;
		else s[i]=0;
		//cout<<s[i];
	}
	bad[n-1]=n-1;
	for(int i=n-2;i>=0;i--){
		bad[i]=i;
		if(s[i]==s[i+1])bad[i]=bad[i+1];
	}
	for(int i=0;i<n;){
		if(s[i]==0){
			i++;
			continue;
		}
		ans++;
		i=max(bad[i]+1,nxt[i]+1);
	}
	//cout<<ans<<endl;
	return ans;
}

int main(){
	ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	cin>>a>>b;
	int ans=solve(a,b);
	for(int i=0;i<n;i++){
		if(a[i]=='0')c+="1";
		else c+="0";
	}
	ans=min(ans,1+solve(c,b));
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...