Submission #236618

#	Time	Username	Problem	Language	Result	Execution time	Memory
236618		muhammad_hokimiyon	Lamps (JOI19_lamps)	C++14	4 / 100	307 ms	27900 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];

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++ ){
        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";
            }
        }
    }
    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: 4 / 4
• Subtask 4: 0 / 49