답안 #769106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769106	2023-06-29T07:44:30 Z	Mohammad_Parsa	Lamps (JOI19_lamps)	C++17	4 / 100	27 ms	18944 KB

lamp

/* 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-