oj.uz

답안 #236624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -