Submission #1181225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181225		LucaIlie	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	148 ms	4660 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct range {
    int l, r;
};

const int MAX_N = 1e5;
const int MAX_D = 1e9;
const int MIN_D = 0;
int n, m;
int s[MAX_N + 1], f[MAX_N + 1];
range rightReach[MAX_N + 1], leftReach[MAX_N + 1];
int dp[MAX_N + 1][2], last[MAX_N + 1][2];

bool solve( int d, bool printSol ) {
    int j = 1;
    for ( int i = 1; i <= n; i++ ) {
        while ( j <= m && f[j] < s[i] - d )
            j++;
        leftReach[i].l = j;
    }
    j = 0;
    for ( int i = 1; i <= n; i++ ) {
        while ( j + 1 <= m && f[j + 1] <= s[i] + d )
            j++;
        rightReach[i].r = j;
    }
    j = 0;
    for ( int i = 1; i <= n; i++ ) {
        while ( j + 1 <= m && f[j + 1] <= s[i] )
            j++;
        leftReach[i].r = j;
    }
    j = 1;
    for ( int i = 1; i <= n; i++ ) {
        while ( j <= m && f[j] < s[i] )
            j++;
        rightReach[i].l = j;
    }

    for ( int i = 0; i <= n; i++ )
        dp[i][0] = dp[i][1] = 0;

    for ( int i = 1; i <= n; i++ ) {
        // am acoperit pana la dp[i - 1]

        //incerc stanga
        if ( leftReach[i].l <= dp[i - 1][0] + 1 ) {
            int k = leftReach[i].r;
            if ( k > dp[i][0] ) {
                dp[i][0] = k;
                last[i][0] = 0;
            }
        }
        if ( leftReach[i].l <= dp[i - 1][1] + 1 ) {
            int k = max( leftReach[i].r, rightReach[i - 1].r );
            if ( k > dp[i][0] ) {
                dp[i][0] = k;
                last[i][0] = 1;
            }
        }

        //incerc dreapta
        for ( int p = 0; p < 2; p++ ) {
            if ( rightReach[i].l <= dp[i - 1][p] + 1 ) {
                int k = rightReach[i].r;
                if ( k > dp[i][1] ) {
                    dp[i][1] = k;
                    last[i][1] = p;
                }
            }
            if ( dp[i - 1][p] > dp[i][1] ) {
                dp[i][1] = dp[i - 1][p];
                last[i][1] = p;
            }
        }
    }

    string sol = "";
    int side = (dp[n][0] > dp[n][1] ? 0 : 1);
    for ( int i = n; i >= 1; i-- ) {
        sol += (side ? 'R' : 'L');
        side = last[i][side];
    }
    reverse( sol.begin(), sol.end() );
    if ( printSol ) 
        cout << sol << "\n";

    #ifdef LOCAL
        printf( "---------D %d--------\n", d );
        for ( int i = 1; i <= n; i++ )
            printf( "%d %d %d %d\n", leftReach[i].l, leftReach[i].r, rightReach[i].l, rightReach[i].r );    
        for ( int i = 0; i <= n; i++ )
            printf( "(%d %d) (%d %d)\n", dp[i][0], last[i][0], dp[i][1], last[i][1] );
    #endif


    return (max( dp[n][0], dp[n][1] ) >= m);
}

int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );

    cin >> n >> m;
    for ( int i = 1; i <= n; i++ )
        cin >> s[i];
    for ( int i = 1; i <= m; i++ )
        cin >> f[i];

    int l = MIN_D - 1, r = MAX_D + 1;
    while ( r - l > 1 ) {
        int mid = (l + r) / 2;
        if ( solve( mid, false ) )
            r = mid;
        else
            l = mid;
    }

    if ( r == MAX_D + 1 )
        cout << "-1\n";
    else {
        cout << r << "\n";
        solve( r, true );
    }

    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 17 / 17
• Subtask 4: 27 / 27
• Subtask 5: 47 / 47