oj.uz

Submission #555476

# Submission time Handle Problem Language Result Execution time Memory
555476 2022-05-01T04:27:22 Z kym Lamps (JOI19_lamps) C++14
4 / 100
 59 ms 51280 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll 
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#define reach 
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> void chmax(T& a, const T b) { a=max(a,b); }
template <typename T> void chmin(T& a, const T b) { a=min(a,b); }
const int MAXN = 1000005;
int n;
char A[MAXN];
char B[MAXN];
int dp[MAXN][3][2]; // {idx, operation 1/2, whether i want to flip}
int32_t main() 
{
	IAMSPEED
	cin >> n;
	FOR(i,1,n) cin >> A[i];
	FOR(i,1,n) cin >> B[i];
	
	FOR(i,0,MAXN-1)FOR(j,0,2)FOR(k,0,1)dp[i][j][k]=oo;
	dp[0][0][0] = 0ll;
	FOR(i,1,n) {
		// do nothing
		if(A[i] == B[i])dp[i][0][0] = min({dp[i-1][0][0], dp[i-1][0][1], dp[i-1][1][0], dp[i-1][1][1], dp[i-1][2][0], dp[i-1][2][1]});
		//flip
		if(A[i] != B[i]){
			//reach
			dp[i][0][1] = min({dp[i-1][0][0] + 1, dp[i-1][0][1], dp[i-1][1][0] + 1, dp[i-1][1][1], dp[i-1][2][0] + 1, dp[i-1][2][1]});
			//db2(i-1,dp[i-1][0][0]);
		}
		//set to 0
		if(B[i] == '0') dp[i][1][0] = min({dp[i-1][0][0] + 1, dp[i-1][0][1] + 1, dp[i-1][1][0], dp[i-1][1][1], dp[i-1][2][0] + 1, dp[i-1][2][1] + 1});
		//set to 0 and flip
		if(B[i] == '0') { //flip FIRST, then set
			chmin(dp[i][1][1], dp[i-1][0][0] + 2);
			chmin(dp[i][1][1], dp[i-1][0][1] + 1);
			chmin(dp[i][1][1], dp[i-1][1][0] + 1);
			if(B[i-1] == '0')chmin(dp[i][1][1], dp[i-1][1][1]);
			else chmin(dp[i][1][1], dp[i-1][1][1] + 2);
			chmin(dp[i][1][1], dp[i-1][2][0] + 2);
			chmin(dp[i][1][1], dp[i-1][2][1] + 1);
		} else { // set FIRST, then FLIP
			chmin(dp[i][1][1], dp[i-1][0][0] + 2);
			chmin(dp[i][1][1], dp[i-1][0][1] + 1);
			chmin(dp[i][1][1], dp[i-1][1][0] + 1);
			if(B[i-1] == '1')chmin(dp[i][1][1], dp[i-1][1][1]);
			else chmin(dp[i][1][1], dp[i-1][1][1] + 2);
			chmin(dp[i][1][1], dp[i-1][2][0] + 2);
			chmin(dp[i][1][1], dp[i-1][2][1] + 1);
		}
		
		
		//set to 1
		if(B[i] == '1') dp[i][2][0] = min({dp[i-1][0][0] + 1, dp[i-1][0][1] + 1, dp[i-1][1][0] + 1, dp[i-1][1][1] + 1, dp[i-1][2][0], dp[i-1][2][1]});
		//set to 1 and flip
		if(B[i] == '1') { //flip FIRST, then set
			chmin(dp[i][2][1], dp[i-1][0][0] + 2);
			chmin(dp[i][2][1], dp[i-1][0][1] + 1);
			chmin(dp[i][2][1], dp[i-1][2][0] + 1);
			if(B[i-1] == '1')chmin(dp[i][1][1], dp[i-1][2][1]);
			else chmin(dp[i][2][1], dp[i-1][2][1] + 2);
			chmin(dp[i][2][1], dp[i-1][1][0] + 2);
			chmin(dp[i][2][1], dp[i-1][1][1] + 1);
		} else { // set FIRST, then FLIP
			chmin(dp[i][2][1], dp[i-1][0][0] + 2);
			chmin(dp[i][2][1], dp[i-1][0][1] + 1);
			chmin(dp[i][2][1], dp[i-1][2][0] + 1);
			if(B[i-1] == '0')chmin(dp[i][1][1], dp[i-1][2][1]);
			else chmin(dp[i][2][1], dp[i-1][2][1] + 2);
			chmin(dp[i][2][1], dp[i-1][1][0] + 2);
			chmin(dp[i][2][1], dp[i-1][1][1] + 1);
		}
		FOR(a,0,2) {
			FOR(b,0,1) {
				db(i);
				db3(dp[i][a][b], a, b);
			}
		}
	}
	int res = oo;
	FOR(i,0,2)FOR(j,0,1)chmin(res,dp[n][i][j]);
	cout << res;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47188 KB Output is correct
2 Correct 20 ms 47180 KB Output is correct
3 Correct 20 ms 47188 KB Output is correct
4 Correct 18 ms 47224 KB Output is correct
5 Correct 20 ms 47332 KB Output is correct
6 Correct 19 ms 47280 KB Output is correct
7 Correct 19 ms 47316 KB Output is correct
8 Correct 19 ms 47276 KB Output is correct
9 Correct 18 ms 47188 KB Output is correct
10 Correct 19 ms 47188 KB Output is correct
11 Correct 18 ms 47240 KB Output is correct
12 Correct 20 ms 47312 KB Output is correct
13 Correct 18 ms 47180 KB Output is correct
14 Correct 19 ms 47196 KB Output is correct
15 Correct 19 ms 47260 KB Output is correct
16 Correct 20 ms 47300 KB Output is correct
17 Correct 19 ms 47188 KB Output is correct
18 Correct 19 ms 47200 KB Output is correct
19 Correct 21 ms 47260 KB Output is correct
20 Correct 21 ms 47204 KB Output is correct
21 Correct 20 ms 47228 KB Output is correct
22 Correct 19 ms 47308 KB Output is correct
23 Correct 20 ms 47304 KB Output is correct
24 Correct 19 ms 47188 KB Output is correct
25 Correct 19 ms 47188 KB Output is correct
26 Correct 21 ms 47352 KB Output is correct
27 Correct 22 ms 47188 KB Output is correct
28 Correct 19 ms 47184 KB Output is correct
29 Correct 20 ms 47196 KB Output is correct
30 Incorrect 19 ms 47276 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47188 KB Output is correct
2 Correct 20 ms 47180 KB Output is correct
3 Correct 20 ms 47188 KB Output is correct
4 Correct 18 ms 47224 KB Output is correct
5 Correct 20 ms 47332 KB Output is correct
6 Correct 19 ms 47280 KB Output is correct
7 Correct 19 ms 47316 KB Output is correct
8 Correct 19 ms 47276 KB Output is correct
9 Correct 18 ms 47188 KB Output is correct
10 Correct 19 ms 47188 KB Output is correct
11 Correct 18 ms 47240 KB Output is correct
12 Correct 20 ms 47312 KB Output is correct
13 Correct 18 ms 47180 KB Output is correct
14 Correct 19 ms 47196 KB Output is correct
15 Correct 19 ms 47260 KB Output is correct
16 Correct 20 ms 47300 KB Output is correct
17 Correct 19 ms 47188 KB Output is correct
18 Correct 19 ms 47200 KB Output is correct
19 Correct 21 ms 47260 KB Output is correct
20 Correct 21 ms 47204 KB Output is correct
21 Correct 20 ms 47228 KB Output is correct
22 Correct 19 ms 47308 KB Output is correct
23 Correct 20 ms 47304 KB Output is correct
24 Correct 19 ms 47188 KB Output is correct
25 Correct 19 ms 47188 KB Output is correct
26 Correct 21 ms 47352 KB Output is correct
27 Correct 22 ms 47188 KB Output is correct
28 Correct 19 ms 47184 KB Output is correct
29 Correct 20 ms 47196 KB Output is correct
30 Incorrect 19 ms 47276 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47308 KB Output is correct
2 Correct 19 ms 47188 KB Output is correct
3 Correct 20 ms 47236 KB Output is correct
4 Correct 20 ms 47312 KB Output is correct
5 Correct 19 ms 47188 KB Output is correct
6 Correct 19 ms 47172 KB Output is correct
7 Correct 57 ms 51148 KB Output is correct
8 Correct 59 ms 51060 KB Output is correct
9 Correct 58 ms 51120 KB Output is correct
10 Correct 59 ms 51096 KB Output is correct
11 Correct 58 ms 51280 KB Output is correct
12 Correct 59 ms 51204 KB Output is correct
13 Correct 57 ms 51084 KB Output is correct
14 Correct 58 ms 51100 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47188 KB Output is correct
2 Correct 20 ms 47180 KB Output is correct
3 Correct 20 ms 47188 KB Output is correct
4 Correct 18 ms 47224 KB Output is correct
5 Correct 20 ms 47332 KB Output is correct
6 Correct 19 ms 47280 KB Output is correct
7 Correct 19 ms 47316 KB Output is correct
8 Correct 19 ms 47276 KB Output is correct
9 Correct 18 ms 47188 KB Output is correct
10 Correct 19 ms 47188 KB Output is correct
11 Correct 18 ms 47240 KB Output is correct
12 Correct 20 ms 47312 KB Output is correct
13 Correct 18 ms 47180 KB Output is correct
14 Correct 19 ms 47196 KB Output is correct
15 Correct 19 ms 47260 KB Output is correct
16 Correct 20 ms 47300 KB Output is correct
17 Correct 19 ms 47188 KB Output is correct
18 Correct 19 ms 47200 KB Output is correct
19 Correct 21 ms 47260 KB Output is correct
20 Correct 21 ms 47204 KB Output is correct
21 Correct 20 ms 47228 KB Output is correct
22 Correct 19 ms 47308 KB Output is correct
23 Correct 20 ms 47304 KB Output is correct
24 Correct 19 ms 47188 KB Output is correct
25 Correct 19 ms 47188 KB Output is correct
26 Correct 21 ms 47352 KB Output is correct
27 Correct 22 ms 47188 KB Output is correct
28 Correct 19 ms 47184 KB Output is correct
29 Correct 20 ms 47196 KB Output is correct
30 Incorrect 19 ms 47276 KB Output isn't correct
31 Halted 0 ms 0 KB -