oj.uz

Submission #769106

# Submission time Handle Problem Language Result Execution time Memory
769106 2023-06-29T07:44:30 Z Mohammad_Parsa Lamps (JOI19_lamps) C++17
4 / 100
 27 ms 18944 KB 
/* 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;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 324 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 324 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 27 ms 18816 KB Output is correct
8 Correct 22 ms 18804 KB Output is correct
9 Correct 22 ms 18844 KB Output is correct
10 Correct 22 ms 18844 KB Output is correct
11 Correct 23 ms 18840 KB Output is correct
12 Correct 26 ms 18832 KB Output is correct
13 Correct 25 ms 18944 KB Output is correct
14 Correct 26 ms 18816 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 324 KB Output isn't correct
14 Halted 0 ms 0 KB -