제출 #236624

#제출 시각아이디문제언어결과실행 시간메모리
236624muhammad_hokimiyonLamps (JOI19_lamps)C++14
0 / 100
1098 ms29800 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast") #define fi first #define se second #define ll long long #define dl double long using namespace std; const int NN = 4e3 + 7; const int N = 1e6 + 7; const int M = 22; const int mod = 1e9 + 7; const ll inf = 1e18 + 7; const dl rf = 1e-14; const int B = sqrt(N); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n; int p1[N]; int p2[N]; int p3[N]; char a[N]; char b[N]; int d[N][3]; vector < pair < int , int > > bl; int get( int l , int r ) { int res = 0; for( int i = 0; i < (int)bl.size(); i++ ){ auto x = bl[i]; if( x.fi >= l && x.fi <= r ){ res += 1; if( i + 1 < (int)bl.size() ){ int j = i + 1; int y; if( b[x.se] == '0' )y = p1[bl[j].fi] - p1[bl[j - 1].se]; else y = p2[bl[j].fi] - p2[bl[j - 1].se]; while( j < (int)bl.size() && bl[j].fi >= l && bl[j].fi <= r && bl[j].fi - bl[j - 1].se == y && b[bl[j].fi] == b[x.se] ){ j += 1; if( b[x.se] == '0' )y = p1[bl[j].fi] - p1[bl[j - 1].se]; else y = p2[bl[j].fi] - p2[bl[j - 1].se]; } i = j - 1; } } } return res; } void solve1() { cin >> n; for( int i = 1; i <= n; i++ ){ cin >> a[i]; } for( int i = 1; i <= n; i++ ){ cin >> b[i]; } for( int i = 1; i <= n; i++ ){ if( a[i] != b[i] )continue; int j = i; while( j <= n && a[j] == b[j] )j += 1; bl.push_back({i , j - 1}); i = j - 1; } for( int i = 1; i < N; i++ ){ for( int j = 0; j < 3; j++ ){ d[i][j] = 1e9; } } for( int i = 1; i <= n; i++ ){ p1[i] = p1[i - 1] + (b[i] == '0'); p2[i] = p2[i - 1] + (b[i] == '1'); p3[i] = p3[i - 1] + (b[i] == a[i]); } for( int i = 1; i <= n; i++ ){ if( a[i] == b[i] ){ for( int j = 0; j < 3; j++ ){ for( int h = 0; h < 3; h++ ){ d[i][j] = min( d[i][j] , d[i - 1][h] ); } //cout << i << " " << j << " " << d[i][j] << "\n"; } }else{ int l = 1 , r = i + 1; while( l < r ){ int m = (l + r) / 2; if( p1[i] - p1[m - 1] == i - m + 1 )r = m; else l = m + 1; } vector < int > v; v.push_back(l); l = 1 , r = i + 1; while( l < r ){ int m = (l + r) / 2; if( p2[i] - p2[m - 1] == i - m + 1 )r = m; else l = m + 1; } v.push_back(l); l = 1 , r = i + 1; while( l < r ){ int m = (l + r) / 2; if( p3[i] - p3[m - 1] > 0 )l = m + 1; else r = m; } v.push_back(l); for( int j = 0; j < 3; j++ ){ if( v[j] == i + 1 )v[j] += 2; for( int h = 0; h < 3; h++ ){ d[i][j] = min( d[i][j] , d[v[j] - 1][h] + 1 ); } //cout << i << " " << j << " " << v[j] << " " << d[i][j] << "\n"; } for( int j = i; j >= 1; j-- ){ int x = 1e9; for( int h = 0; h < 3; h++ )x = min( x , d[j - 1][h] ); d[i][2] = min( d[i][2] , get( j , i ) + 1 + x ); } } } cout << min({ d[n][0] , d[n][1] , d[n][2] }); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen( "input.txt" , "r" , stdin ); //freopen( "output.txt" , "w" , stdout ); int cghf = 1;//cin >> cghf; while( cghf-- ){ solve1(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...