Submission #253139

#	Time	Username	Problem	Language	Result	Execution time	Memory
253139		Dilshod_Imomov	Lamps (JOI19_lamps)	C++17	47 / 100	1101 ms	30668 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;

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];
string a, b;

int get( int i, int x ) {
	vector < int > v = vc[x]; 
	if ( (int)v.size() == 0 ) {
		int mn = 1e9;
		for ( int j = 0; j < 16; j++ ) {
			mn = min( mn, dp[i - 1][j] );
		}
		return mn + (a[i] != b[i]);
	}
	int mn = 1e9;
	for ( int y = 0; y < 16; y++ ) {
		vector < int > u = vc[y]; 
		int vsz = v.size(), usz = u.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++ ) {
    		vector < int > v = vc[i], u = vc[j];
    		int vsz = v.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( 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 ) {
					mx = max( mx, cnt );
				}
			}
			cnt[i][j] = mx;
    	}
    }
    for ( int j = 0; j < 16; j++ ) {
    	vector < int > v = vc[j]; 
		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][j] = 1e9;
			continue;
		}
    	dp[0][j] = v.size();
    }
    if ( a[0] != b[0] ) {
    	dp[0][0] = 1;
    }
    for ( int i = 1; i < n; i++ ) {
    	for ( int ind = 0; ind < 16; ind++ ) {
    		vector < int > v = vc[ind]; 
    		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][ind] = 1e9;
    			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 = 1e9;
    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: 0 / 4
• Subtask 4: 0 / 49