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...