This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// # pragma GCC optimize "-O3"
# define int long long
using namespace std;
const int N = 1e6 + 7;
const int mod = 1e9;
vector < vector < int > > vc = { {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2},
{1, 2, 3}, { 1, 3, 2 }, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} };
map < int, map < vector < int >, int > > dp;
int n;
string a, b;
int get( int i, vector < int > v ) {
if ( (int)v.size() == 0 ) {
int mn = 1e9;
for ( auto u: vc ) {
mn = min( mn, dp[i - 1][u] );
}
return mn + (a[i] != b[i]);
}
int mn = 1e9;
for ( auto u: vc ) {
int vsz = v.size(), usz = u.size();
if ( vsz <= usz ) {
for ( int mask = 0; mask < (1 << vsz); mask++ ) {
vector < int > x;
int cnt = 0;
for ( int bit = 0; bit < 3; bit++ ) {
if ( (mask >> bit) & 1 ) {
x.push_back( v[bit] );
cnt++;
}
}
int ok = 0;
if ( cnt ) {
int ind = 0;
for ( auto z: u ) {
if ( ind < cnt && z == x[ind] ) {
ind++;
}
}
if ( ind == cnt ) {
ok = 1;
}
}
if ( ok ) {
mn = min( mn, dp[i - 1][u] + vsz - cnt );
}
else {
mn = min( mn, dp[i - 1][u] + vsz );
}
}
}
else {
for ( int mask = 0; mask < (1 << usz); mask++ ) {
vector < int > x;
int cnt = 0;
for ( int bit = 0; bit < 3; bit++ ) {
if ( (mask >> bit) & 1 ) {
x.push_back( u[bit] );
cnt++;
}
}
int ok = 0;
if ( cnt ) {
int ind = 0;
for ( auto z: v ) {
if ( ind < cnt && z == x[ind] ) {
ind++;
}
}
if ( ind == cnt ) {
ok = 1;
}
}
if ( ok ) {
mn = min( mn, dp[i - 1][u] + vsz - cnt );
}
else {
mn = min( mn, dp[i - 1][u] + vsz );
}
}
}
}
return mn;
}
int32_t main() {
speed;
cin >> n;
cin >> a >> b;
for ( auto v: vc ) {
char x = a[0];
for ( auto j: v ) {
if ( j == 1 ) {
x = '0';
}
else if ( j == 2 ) {
x = '1';
}
else {
if ( x == '0' ) {
x = '1';
}
else {
x = '0';
}
}
}
if ( x != b[0] ) {
dp[0][v] = 1e9;
continue;
}
dp[0][v] = v.size();
}
if ( a[0] != b[0] ) {
dp[0][{}] = 1;
}
for ( int i = 1; i < n; i++ ) {
for ( auto v: vc ) {
char x = a[i];
for ( auto j: v ) {
if ( j == 1 ) {
x = '0';
}
else if ( j == 2 ) {
x = '1';
}
else {
if ( x == '0' ) {
x = '1';
}
else {
x = '0';
}
}
}
if ( x != b[i] ) {
dp[i][v] = 1e9;
continue;
}
dp[i][v] = get( i, v );
/*for ( auto j: v ) {
cout << j << ' ';
}
cout << '\n';
cout << i << ' ' << dp[i][v] << '\n';
cout << "------------\n";*/
}
}
int mn = 1e9;
for ( auto v: vc ) {
mn = min( mn, dp[n - 1][v] );
}
cout << mn << '\n';
}
/*
8
11011100
01101001
13
1010010010100
0000111001011
18
001100010010000110
110110001000100101
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |