Submission #410312

#	Time	Username	Problem	Language	Result	Execution time	Memory
410312		amoo_safar	Lamps (JOI19_lamps)	C++17	100 / 100	176 ms	4456 KiB

lamp

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int dp[4][2];
int nx[4][2];


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	str A, B;
	cin >> n;
	cin >> A >> B;

	memset(dp, 31, sizeof dp);
	dp[0][0] = 0;
	for(int i = 0; i < n; i++){
		int nw = A[i] - '0';
		int rq = B[i] - '0';
		memset(nx, 31, sizeof nx);
		for(int bl = 0; bl < 4; bl ++) for(int xo = 0; xo < 2; xo ++) for(int set = 0; set < 3; set ++){
			int co = set == 2 ? nw : set;
			
			int xxor = co != rq;
			int nw_bl = 1;
			int la = -1;
			if(i > 0){
				if(bl > 0)
					la = (B[i-1]-'0') ^ xo;
			}
			if(set == 2) nw_bl = 0;
			else {
				if(i == 0)
					nw_bl = 1;
				else
					nw_bl = bl + (la != set);
			}
			bool change = nw_bl != bl;

			if(nw_bl == 4)
				nw_bl = 2;
			nx[nw_bl][xxor] = min(nx[nw_bl][xxor], dp[bl][xo] + (((nw_bl == 1) || (nw_bl == 2)) && change) + (xxor > xo));
		}
		swap(nx, dp);
	}
	int ans = n;
	for(int i = 0; i < 8; i++)
		ans = min(ans, dp[i >> 1][i & 1]);
	cout << ans << '\n';
	return 0;
}
/*
7
1010010
0000111

4
1010
0000

*/

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