oj.uz

Submission #236624

# Submission time Handle Problem Language Result Execution time Memory
236624 2020-06-02T15:54:37 Z muhammad_hokimiyon Lamps (JOI19_lamps) C++14
0 / 100
 1000 ms 29800 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12160 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 11 ms 12160 KB Output is correct
7 Correct 12 ms 12160 KB Output is correct
8 Correct 11 ms 12160 KB Output is correct
9 Correct 11 ms 12160 KB Output is correct
10 Correct 11 ms 12160 KB Output is correct
11 Correct 11 ms 12160 KB Output is correct
12 Incorrect 11 ms 12160 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12160 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 11 ms 12160 KB Output is correct
7 Correct 12 ms 12160 KB Output is correct
8 Correct 11 ms 12160 KB Output is correct
9 Correct 11 ms 12160 KB Output is correct
10 Correct 11 ms 12160 KB Output is correct
11 Correct 11 ms 12160 KB Output is correct
12 Incorrect 11 ms 12160 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 10 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 11 ms 12160 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 11 ms 12160 KB Output is correct
7 Correct 54 ms 25720 KB Output is correct
8 Execution timed out 1098 ms 29800 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12160 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 11 ms 12160 KB Output is correct
7 Correct 12 ms 12160 KB Output is correct
8 Correct 11 ms 12160 KB Output is correct
9 Correct 11 ms 12160 KB Output is correct
10 Correct 11 ms 12160 KB Output is correct
11 Correct 11 ms 12160 KB Output is correct
12 Incorrect 11 ms 12160 KB Output isn't correct
13 Halted 0 ms 0 KB -