제출 #236624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236624		muhammad_hokimiyon	Lamps (JOI19_lamps)	C++14	0 / 100	1098 ms	29800 KiB

lamp

#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();
    }
}

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