Submission #1101554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101554		thelonewolf	Lamps (JOI19_lamps)	C++14	4 / 100	19 ms	23832 KiB

lamp

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define pir pair<int,int>
using namespace std;
const int maxn = 1e6 + 5;

int dp[maxn],lst[maxn][3],nxt[maxn];
bool a[maxn],b[maxn];

void input(int n){
	string s;
	cin >> s;
	
	for (int i = 1 ; i <= n ; i++)
	  a[i] = s[i - 1] - 48;
	
	cin >> s;
	for (int i = 1 ; i <= n ; i++)
	  b[i] = s[i - 1] - 48;
}

void prepare(int n){
	for (int id = 0 ; id <= 3 ; id++)
	  for (int i = 0 ; i <= n ; i++) lst[i][id] = -1;
	
	for (int i = 0 ; i <= n ; i++) nxt[i] = -1;
	
	for (int i = 1 ; i <= n ; i++){
		//lst[0]
		if (b[i])
		  lst[i][0] = -1;
		else
		  lst[i][0] = (lst[i - 1][0] == -1) ? i : lst[i - 1][0];
	
        if (!b[i])
          lst[i][1] = -1;
        else
          lst[i][1] = (lst[i - 1][1] == -1) ? i : lst[i - 1][1];
        
        
        if (a[i] == b[i])
          lst[i][2] = -1;
        else
          lst[i][2] = (lst[i - 1][2] == -1) ? i : lst[i - 1][2];
        
        if (a[i] != b[i])
          nxt[i] = -1;
        else
          nxt[i] = (nxt[i - 1] == -1) ? i : nxt[i - 1];
	}
	
	for (int i = 1 ; i <= n ; i++) dp[i] = n + 1;
}

void solve(int n){
	for (int i = 1 ; i <= n ; i++){
		for (int id = 0 ; id <= 2 ; id++)
		  if (lst[i][id] != -1)
		    dp[i] = min(dp[i],dp[lst[i][id] - 1] + 1);
		
		if (nxt[i] != -1)
			dp[i] = min(dp[i],dp[nxt[i] - 1]);
		
		if (lst[i][2] != -1){
			//xor
			int p = lst[i][2] - 1;
			
			if (lst[p][0] != -1){
				int p1 = lst[p][0] - 1;
				
				if (a[p1] != b[p1])
				  dp[i] = min(dp[i],dp[p1] + 1);
			}
			
			if (lst[p][1] != -1){
				int p1 = lst[p][1] - 1;
				
				if (a[p1] != b[p1])
				  dp[i] = min(dp[i],dp[p1] + 1);
			}
		}
		
		dp[i] = min(dp[i],dp[i - 1] + 1);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n;
	input(n);
	
	prepare(n);
	solve(n);
	
	cout << dp[n];

	return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49