#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] == '1';
if (type == 3 && type2 == 3)return a[w] == b[w];
return oper(type2, 3, w);
}
int main() {
int n, i, j, k, p, q; 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 < 3; j++) {
for (k = 0; k < 3; 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));
D[i][j][k] = min(D[i][j][k], D[i - 1][k][3] + (j != 3));
}
}
D[i][j][3] = 1e9;
if (oper(j, 3, i)) {
for (p = 0; p < 4; p++)D[i][j][3] = min(D[i][j][3], D[i - 1][j][p]);
for (p = 0; p < 3; p++)D[i][j][3] = min(D[i][j][3], D[i - 1][p][j]);
for (p = 0; p < 4; p++) {
for (q = 0; q < 4; q++) {
D[i][j][3] = min(D[i][j][3], D[i - 1][p][q] + 1);
}
}
}
}
for (j = 0; j < 3; j++)D[i][3][j] = 1e9;
D[i][3][3] = 1e9;
for (j = 0; j < 4; j++) for (k = 0; k < 4; k++) {
if (oper(3, 3, i)) D[i][3][3] = min(D[i][3][3], D[i - 1][j][k]);
}
}
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
lamp.cpp: In function 'int main()':
lamp.cpp:17:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, i, j, k, p, q; scanf("%d%s%s", &n, a + 1, b + 1);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
128 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
256 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| 6 |
Correct |
4 ms |
256 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
4 ms |
256 KB |
Output is correct |
| 10 |
Correct |
5 ms |
380 KB |
Output is correct |
| 11 |
Correct |
5 ms |
248 KB |
Output is correct |
| 12 |
Correct |
4 ms |
256 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
5 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
376 KB |
Output is correct |
| 16 |
Correct |
5 ms |
380 KB |
Output is correct |
| 17 |
Correct |
5 ms |
248 KB |
Output is correct |
| 18 |
Correct |
4 ms |
376 KB |
Output is correct |
| 19 |
Correct |
5 ms |
376 KB |
Output is correct |
| 20 |
Correct |
4 ms |
376 KB |
Output is correct |
| 21 |
Correct |
4 ms |
256 KB |
Output is correct |
| 22 |
Correct |
5 ms |
380 KB |
Output is correct |
| 23 |
Correct |
5 ms |
256 KB |
Output is correct |
| 24 |
Correct |
5 ms |
256 KB |
Output is correct |
| 25 |
Correct |
5 ms |
376 KB |
Output is correct |
| 26 |
Correct |
4 ms |
256 KB |
Output is correct |
| 27 |
Correct |
4 ms |
256 KB |
Output is correct |
| 28 |
Correct |
5 ms |
256 KB |
Output is correct |
| 29 |
Correct |
4 ms |
256 KB |
Output is correct |
| 30 |
Correct |
4 ms |
256 KB |
Output is correct |
| 31 |
Correct |
5 ms |
256 KB |
Output is correct |
| 32 |
Correct |
4 ms |
376 KB |
Output is correct |
| 33 |
Correct |
4 ms |
256 KB |
Output is correct |
| 34 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
128 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
256 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| 6 |
Correct |
4 ms |
256 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
4 ms |
256 KB |
Output is correct |
| 10 |
Correct |
5 ms |
380 KB |
Output is correct |
| 11 |
Correct |
5 ms |
248 KB |
Output is correct |
| 12 |
Correct |
4 ms |
256 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
5 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
376 KB |
Output is correct |
| 16 |
Correct |
5 ms |
380 KB |
Output is correct |
| 17 |
Correct |
5 ms |
248 KB |
Output is correct |
| 18 |
Correct |
4 ms |
376 KB |
Output is correct |
| 19 |
Correct |
5 ms |
376 KB |
Output is correct |
| 20 |
Correct |
4 ms |
376 KB |
Output is correct |
| 21 |
Correct |
4 ms |
256 KB |
Output is correct |
| 22 |
Correct |
5 ms |
380 KB |
Output is correct |
| 23 |
Correct |
5 ms |
256 KB |
Output is correct |
| 24 |
Correct |
5 ms |
256 KB |
Output is correct |
| 25 |
Correct |
5 ms |
376 KB |
Output is correct |
| 26 |
Correct |
4 ms |
256 KB |
Output is correct |
| 27 |
Correct |
4 ms |
256 KB |
Output is correct |
| 28 |
Correct |
5 ms |
256 KB |
Output is correct |
| 29 |
Correct |
4 ms |
256 KB |
Output is correct |
| 30 |
Correct |
4 ms |
256 KB |
Output is correct |
| 31 |
Correct |
5 ms |
256 KB |
Output is correct |
| 32 |
Correct |
4 ms |
376 KB |
Output is correct |
| 33 |
Correct |
4 ms |
256 KB |
Output is correct |
| 34 |
Correct |
5 ms |
256 KB |
Output is correct |
| 35 |
Correct |
5 ms |
504 KB |
Output is correct |
| 36 |
Correct |
5 ms |
504 KB |
Output is correct |
| 37 |
Correct |
5 ms |
376 KB |
Output is correct |
| 38 |
Correct |
5 ms |
376 KB |
Output is correct |
| 39 |
Correct |
5 ms |
376 KB |
Output is correct |
| 40 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 41 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
504 KB |
Output is correct |
| 4 |
Correct |
4 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| 6 |
Correct |
5 ms |
256 KB |
Output is correct |
| 7 |
Correct |
240 ms |
64864 KB |
Output is correct |
| 8 |
Correct |
253 ms |
64888 KB |
Output is correct |
| 9 |
Correct |
266 ms |
65016 KB |
Output is correct |
| 10 |
Correct |
273 ms |
64900 KB |
Output is correct |
| 11 |
Correct |
254 ms |
64888 KB |
Output is correct |
| 12 |
Correct |
283 ms |
65000 KB |
Output is correct |
| 13 |
Correct |
255 ms |
64888 KB |
Output is correct |
| 14 |
Correct |
262 ms |
64888 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
128 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
256 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| 6 |
Correct |
4 ms |
256 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
4 ms |
256 KB |
Output is correct |
| 10 |
Correct |
5 ms |
380 KB |
Output is correct |
| 11 |
Correct |
5 ms |
248 KB |
Output is correct |
| 12 |
Correct |
4 ms |
256 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
5 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
376 KB |
Output is correct |
| 16 |
Correct |
5 ms |
380 KB |
Output is correct |
| 17 |
Correct |
5 ms |
248 KB |
Output is correct |
| 18 |
Correct |
4 ms |
376 KB |
Output is correct |
| 19 |
Correct |
5 ms |
376 KB |
Output is correct |
| 20 |
Correct |
4 ms |
376 KB |
Output is correct |
| 21 |
Correct |
4 ms |
256 KB |
Output is correct |
| 22 |
Correct |
5 ms |
380 KB |
Output is correct |
| 23 |
Correct |
5 ms |
256 KB |
Output is correct |
| 24 |
Correct |
5 ms |
256 KB |
Output is correct |
| 25 |
Correct |
5 ms |
376 KB |
Output is correct |
| 26 |
Correct |
4 ms |
256 KB |
Output is correct |
| 27 |
Correct |
4 ms |
256 KB |
Output is correct |
| 28 |
Correct |
5 ms |
256 KB |
Output is correct |
| 29 |
Correct |
4 ms |
256 KB |
Output is correct |
| 30 |
Correct |
4 ms |
256 KB |
Output is correct |
| 31 |
Correct |
5 ms |
256 KB |
Output is correct |
| 32 |
Correct |
4 ms |
376 KB |
Output is correct |
| 33 |
Correct |
4 ms |
256 KB |
Output is correct |
| 34 |
Correct |
5 ms |
256 KB |
Output is correct |
| 35 |
Correct |
5 ms |
504 KB |
Output is correct |
| 36 |
Correct |
5 ms |
504 KB |
Output is correct |
| 37 |
Correct |
5 ms |
376 KB |
Output is correct |
| 38 |
Correct |
5 ms |
376 KB |
Output is correct |
| 39 |
Correct |
5 ms |
376 KB |
Output is correct |
| 40 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 41 |
Halted |
0 ms |
0 KB |
- |
