oj.uz

Submission #210832

# Submission time Handle Problem Language Result Execution time Memory
210832 2020-03-18T19:05:09 Z amiratou Lamps (JOI19_lamps) C++14
4 / 100
 50 ms 16200 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
//#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int t[1000002],pre[1000002],dp[1000002];
int n;
string A,B;
void pro(){
	for (int i = n-1; i >= 0; i--)
	{
		int h=(int)(A[i]-'0')^(int)(B[i]-'0');
		if(!h)t[i]=-1;
		else if(i==(n-1)||t[i+1]==-1)t[i]=i;
		else t[i]=t[i+1];
		if(i==(n-1)||(B[i]!=B[i+1]))pre[i]=i;
		else pre[i]=pre[i+1];
		dp[i+1]=INF;
	}
}
int solve(){
	dp[0]=0;
	for (int i = 0; i < n; ++i)
	{
		if(A[i]==B[i])dp[i+1]=min(dp[i+1],dp[i]);
		else{
			dp[t[i]+1]=min(dp[t[i]+1],dp[i]+1);
			dp[pre[i]+1]=min(dp[pre[i]+1],dp[i]+1);
		}
	}
	return dp[n];
}
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	cin>>n;
	cin>>A>>B;
	pro();
	int ans=solve();
	for (int i = 0; i < n; ++i)
		A[i]=(char)(1-(int)(A[i]-'0')+'0'),pre[i]=t[i]=0;
	pro();
	cout<<min(ans,solve()+1);
	return 0;
}
//long long
//array bounds
//special cases
//binary search

Subtask #1
0 / 6.0

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

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 7 ms 276 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 6 ms 404 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 6 ms 404 KB Output is correct
13 Incorrect 6 ms 376 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 6 ms 276 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 276 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 6 ms 380 KB Output is correct
7 Correct 47 ms 16124 KB Output is correct
8 Correct 47 ms 16196 KB Output is correct
9 Correct 46 ms 16072 KB Output is correct
10 Correct 47 ms 16172 KB Output is correct
11 Correct 47 ms 16184 KB Output is correct
12 Correct 46 ms 16072 KB Output is correct
13 Correct 50 ms 16200 KB Output is correct
14 Correct 47 ms 16068 KB Output is correct

Subtask #4
0 / 49.0

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