oj.uz

Submission #1101554

# Submission time Handle Problem Language Result Execution time Memory
1101554 2024-10-16T10:01:43 Z thelonewolf Lamps (JOI19_lamps) C++14
4 / 100
 19 ms 23832 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 1 ms 6480 KB Output is correct
3 Correct 2 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 1 ms 6480 KB Output is correct
8 Correct 1 ms 6480 KB Output is correct
9 Correct 1 ms 6480 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct
11 Correct 1 ms 6480 KB Output is correct
12 Correct 1 ms 6648 KB Output is correct
13 Correct 1 ms 6480 KB Output is correct
14 Correct 1 ms 6480 KB Output is correct
15 Correct 1 ms 6480 KB Output is correct
16 Incorrect 2 ms 6692 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 1 ms 6480 KB Output is correct
3 Correct 2 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 1 ms 6480 KB Output is correct
8 Correct 1 ms 6480 KB Output is correct
9 Correct 1 ms 6480 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct
11 Correct 1 ms 6480 KB Output is correct
12 Correct 1 ms 6648 KB Output is correct
13 Correct 1 ms 6480 KB Output is correct
14 Correct 1 ms 6480 KB Output is correct
15 Correct 1 ms 6480 KB Output is correct
16 Incorrect 2 ms 6692 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 1 ms 6480 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 16 ms 23824 KB Output is correct
8 Correct 18 ms 23832 KB Output is correct
9 Correct 16 ms 23832 KB Output is correct
10 Correct 19 ms 23832 KB Output is correct
11 Correct 17 ms 23832 KB Output is correct
12 Correct 16 ms 23832 KB Output is correct
13 Correct 16 ms 23832 KB Output is correct
14 Correct 18 ms 23824 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 1 ms 6480 KB Output is correct
3 Correct 2 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 1 ms 6480 KB Output is correct
8 Correct 1 ms 6480 KB Output is correct
9 Correct 1 ms 6480 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct
11 Correct 1 ms 6480 KB Output is correct
12 Correct 1 ms 6648 KB Output is correct
13 Correct 1 ms 6480 KB Output is correct
14 Correct 1 ms 6480 KB Output is correct
15 Correct 1 ms 6480 KB Output is correct
16 Incorrect 2 ms 6692 KB Output isn't correct
17 Halted 0 ms 0 KB -