Submission #156276

#	Time	Username	Problem	Language	Result	Execution time	Memory
156276		popovicirobert	Lamps (JOI19_lamps)	C++14	100 / 100	362 ms	67036 KiB

lamp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x)) 
    
using namespace std;

const int MAXN = (int) 1e6 + 5;

char A[MAXN + 1], B[MAXN + 1];

int dp[MAXN + 1][4][4];

int aux[2][4][4];
   
int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
		
	cin >> n >> A + 1 >> B + 1;

	for(i = 0; i <= n; i++) {
		A[i] -= '0', B[i] -= '0';
		for(int a = 0; a <= 3; a++) {
			for(int b = 0; b <= 3; b++) {
				dp[i][a][b] = MAXN;
			}
		}
	}

	auto get = [&](int x, int y) {
		if(y == 0) return x;
		if(y == 1) return 0;
		if(y == 2) return 1;
		return x ^ 1;
	};

	auto check = [&](int x, int y, int z) {
		return get(get(x, y), z);
	};

	for(i = 0; i < 2; i++) {
		for(int a = 0; a <= 3; a++) {
			for(int b = 0; b <= 3; b++) {
				aux[i][a][b] = check(i, a, b);
			}
		}
	}

	dp[0][0][0] = 0;

	for(i = 1; i <= n; i++) {
		for(int a = 0; a <= 3; a++) {
			for(int b = (a > 0); b <= 3; b++) {
				if(dp[i - 1][a][b] == MAXN) continue;

				for(int c = 0; c <= 3; c++) {
					for(int d = (c > 0); d <= 3; d++) {
						if(aux[A[i]][c][d] != B[i]) continue;

						int cnt = MAXN;
						if(a == c && b == d) {
							cnt = 0;
						}
						else {
							if(a == c || b == c) {
								cnt = min(cnt, (int)(d > 0));
							}
							if(a == d || b == d) {
								cnt = min(cnt, (int)(c > 0));
							}
							cnt = min(cnt, (c > 0) + (d > 0));
						}
						dp[i][c][d] = min(dp[i][c][d], dp[i - 1][a][b] + cnt);
					}
				}
			}
		}
	}

	int ans = MAXN;
	for(int a = 0; a <= 3; a++) {
		for(int b = (a > 0); b <= 3; b++) {
			if(check(A[n], a, b) == B[n])
				ans = min(ans, dp[n][a][b]);
		}
	}

	cout << ans;
            
	return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:23:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  cin >> n >> A + 1 >> B + 1;
              ~~^~~
lamp.cpp:23:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  cin >> n >> A + 1 >> B + 1;
                       ~~^~~
lamp.cpp:62:18: warning: array subscript has type 'char' [-Wchar-subscripts]
       if(aux[A[i]][c][d] != B[i]) continue;
                  ^

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