Submission #204060

#	Time	Username	Problem	Language	Result	Execution time	Memory
204060		ics0503	Lamps (JOI19_lamps)	C++17	10 / 100	200 ms	67064 KiB

lamp

#include<stdio.h>

char a[1212121], b[1212121];
int D[1212121][4][4];
int min(int a, int b) { if (a < b)return a; return b; }
bool oper(int type, int type2, int w) {
	if (type == 0)return b[w] == '0';
	if (type == 1)return b[w] == '1';
	if (type == 2 && type2 == 3)return b[w] != a[w];
	if (type == 2 && type2 == 2)return b[w] == a[w];
	if (type == 2 && type2 == 1)return b[w] == '0';
	if (type == 2 && type2 == 0)return b[w] == '0';
	if (type == 3 && type2 == 3)return a[w] == b[w];
	return oper(type2, 3, w);
}
int main() {
	int n, i, j, k, p; scanf("%d%s%s", &n,a+1,b+1);
	for (i = 0; i < 4; i++)for (j = 0; j < 4; j++)D[0][i][j] = 1e9;
	D[0][3][3] = 0;
	for (i = 1; i <= n; i++) {
		for (j = 0; j < 4; j++) {
			for (k = 0; k < 4; k++) {
				D[i][j][k] = 1e9;
				if (oper(j, k, i)) {
					D[i][j][k] = D[i - 1][j][k];
					for (p = 0; p < 4; p++)
						D[i][j][k] = min(D[i][j][k], D[i - 1][p][k] + (j != 3));
					if (k == 3) {
						for (p = 0; p < 4; p++)
							D[i][j][3] = min(D[i][j][3], D[i - 1][p][j] + (p == 3));
					}
					for (p = 0; p < 4; p++)
						D[i][j][k] = min(D[i][j][k], D[i - 1][k][p] + (j != 3));
				}
			}
		}
	}
	int ans = 1e9;
	for (i = 0; i < 4; i++)for (j = 0; j < 4; j++)ans = min(ans, D[n][i][j]);
	printf("%d", ans);

	return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:17:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, i, j, k, p; scanf("%d%s%s", &n,a+1,b+1);
                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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