Submission #1181209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181209		LucaIlie	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	126 ms	3492 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];
char last[MAX_N + 1];

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;
        last[i] = 'L';
    }

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

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

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

    string sol = "";
    for ( int i = 1; i <= n; i++ )
        sol += last[i];
    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 %c\n", dp[i], last[i] );
    #endif


    return (dp[n] >= 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: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47