#include <bits/stdc++.h>
#define BLACK '0'
#define WHITE '1'
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n;
string A, B;
cin >> A >> B;
int colour = B[0];
vector<int> types;
///0 - correct, 1 - all wrong, 2 - prefix wrong, 3 - suffix wrong, 4 - prefix & suffix wrong, 5 - rojak
bool firstCorrect = (A[0] == B[0]);
bool lastCorrect = false;
int flip = 0;
for(int i = 0;i < n;i++){
if(i == n-1 || B[i] != B[i+1]){
lastCorrect = (A[i] == colour);
int type = 0;
if(flip == 0){
if(lastCorrect) type = 0;
else type = 1;
}
else if(flip == 1){
if(firstCorrect) type = 3;
else type = 2;
}
else if(flip == 2){
if(!firstCorrect && !lastCorrect) type = 4;
else type = 5;
}
else type = 5;
types.push_back(type);
if(colour == WHITE) colour = BLACK;
else colour = WHITE;
flip = 0;
if(i != n-1) firstCorrect = (A[i+1] == colour);
}
else if(A[i] != A[i+1]) flip++;
}
//for(int x : types) cout << x << " "; cout << "\n";
auto backward = [&](int i){
for(int j = i - 1;j >= 0;j--){
if(types[j] == 0 || types[j] == 2) break;
else if(types[j] == 1) types[j] = 0;
else if(types[j] == 3) {types[j] = 0; break;}
else if(types[j] == 4) {types[j] = 2; break;}
}
};
auto forward = [&](int i){
for(int j = i + 1;j < (int) types.size();j++){
if(types[j] == 0 || types[j] == 3) break;
else if(types[j] == 1) types[j] = 0;
else if(types[j] == 2) {types[j] = 0; break;}
else if(types[j] == 4) {types[j] = 3; break;}
}
};
int ans = 0;
while(true){
bool has = false;
for(int i = 0;i < n;i++){
if(types[i] == 2 || types[i] == 1 || types[i] == 3){
ans++;
if(types[i] == 2 || types[i] == 1) backward(i);
if(types[i] == 3 || types[i] == 1) forward(i);
has = true;
types[i] = 0;
}
}
if(!has) break;
}
//cout << ans << "\n";
for(int x : types){
if(x != 0) ans++;
}
cout << ans << "\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
308 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Runtime error |
15 ms |
6612 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
