Submission #253140

#	Time	Username	Problem	Language	Result	Execution time	Memory
253140		Dilshod_Imomov	Lamps (JOI19_lamps)	C++17	100 / 100	320 ms	67152 KiB

lamp

# 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 + 7;

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, cnt[20][20], dp[N][16], change[2][16];
string a, b;

int get( int i, int x ) {
	if ( (int)vc[x].size() == 0 ) {
		int mn = N;
		for ( int j = 0; j < 16; j++ ) {
			mn = min( mn, dp[i - 1][j] );
		}
		return mn + (a[i] != b[i]);
	}
	int mn = N;
	for ( int y = 0; y < 16; y++ ) {
		int vsz = vc[x].size(), usz = vc[y].size();
		if ( vsz <= usz ) {
			mn = min( mn, dp[i - 1][y] + vsz - cnt[x][y] );
		}
		else {
			mn = min( mn, dp[i - 1][y] + vsz - cnt[y][x] );
		}
	}
	return mn;
}

int32_t main() {
    speed;
    cin >> n;
    cin >> a >> b;
    for ( int i = 0; i < 16; i++ ) {
    	for ( int j = 0; j < 16; j++ ) {
    		int vsz = vc[i].size(), mx = 0; 
			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( vc[i][bit] );
						cnt++;
					}
				}
				int ok = 0;
				if ( cnt ) {
					int ind = 0;
					for ( auto z: vc[j] ) {
						if ( ind < cnt && z == x[ind] ) {
							ind++;
						}
					}
					if ( ind == cnt ) {
						ok = 1;
					}
				}
				if ( ok ) {
					mx = max( mx, cnt );
				}
			}
			cnt[i][j] = mx;
    	}
    }
    for ( int i = 0; i < 16; i++ ) {
		char x = '0', y = '1';
		for ( auto j: vc[i] ) {
			if ( j == 1 ) {
				x = '0';
				y = '0';
			}
			else if ( j == 2 ) {
				x = '1';
				y = '1';
			}
			else {
				if ( y == '0' ) {
					y = '1';
				}
				else {
					y = '0';
				}
				if ( x == '0' ) {
					x = '1';
				}
				else {
					x = '0';
				}
			}
		}
    	change[0][i] = x - '0';
    	change[1][i] = y - '0';
    }
    for ( int j = 0; j < 16; j++ ) {
		if ( ('0' + change[a[0] - '0'][j]) != b[0] ) {
			dp[0][j] = N;
			continue;
		}
    	dp[0][j] = vc[j].size();
    }
    if ( a[0] != b[0] ) {
    	dp[0][0] = 1;
    }
    for ( int i = 1; i < n; i++ ) {
    	for ( int ind = 0; ind < 16; ind++ ) {
    		if ( ('0' + change[a[i] - '0'][ind]) != b[i] ) {
    			dp[i][ind] = N;
    			continue;
    		}
    		dp[i][ind] = get( i, ind );
    		/*for ( auto j: v ) {
    			cout << j << ' ';
    		}
    		cout << '\n';
    		cout << i << ' ' << dp[i][v] << '\n';
    		cout << "------------\n";*/
    	}
    }
    int mn = N;
    for ( int i = 0; i < 16; i++ ) {
    	mn = min( mn, dp[n - 1][i] );
    }
    cout << mn << '\n';
}
/*
8
11011100
01101001

13
1010010010100
0000111001011

18
001100010010000110
110110001000100101
*/

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