Submission #105070

#	Time	Username	Problem	Language	Result	Execution time	Memory
105070		IOrtroiii	Lamps (JOI19_lamps)	C++14	100 / 100	109 ms	14844 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

const int N = 1000100;

int n;
char from[N], to[N];
int f[N][3];

char get(char a,int x) {
	if (x == 0) return '0';
	if (x == 1) return '1';
	if (x == 2) return a;
}

int main() {
	scanf("%d %s %s", &n, from + 1, to + 1);
	f[0][2] = 0;
	f[0][0] = f[0][1] = n + 5;
	for (int i = 1; i <= n; ++i) {
		for (int x = 0; x < 3; ++x) {
			f[i][x] = n + 5;
		}
		for (int x = 0; x < 3; ++x) {
			for (int xx = 0; xx < 3; ++xx) {
				int nw = f[i - 1][x];
				if (x != xx && xx != 2) {
					++nw;
				}
				if ((i == 1 || get(from[i - 1], x) == to[i - 1]) && get(from[i], xx) != to[i]) {
					++nw;
				}
				f[i][xx] = min(f[i][xx], nw);
			}
		}
	}
	int ans = n + 5;
	for (int x = 0; x < 3; ++x) {
		ans = min(ans, f[n][x]);
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

lamp.cpp: In function 'char get(char, int)':
lamp.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
lamp.cpp: In function 'int main()':
lamp.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %s %s", &n, from + 1, to + 1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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