Submission #1181197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181197		LucaIlie	Sprinklers (CEOI24_sprinklers)	C++20	0 / 100	2095 ms	8008 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[1001][1001];
char last[1001][1001];

bool solve( int d, bool printSol ) {
    int j = 0;
    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 = 0;
    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++ ) {
        for ( int j = 0; j <= m; j++ )
            dp[i][j] = (j == 0), last[i][j] = 'L';
    }

    for ( int i = 1; i <= n; i++ ) {
        // i merge la stanga
        for ( int j = 0; j < m; j++ ) {
            //eu am acoperit pana la j deci acopar (j+1, leftReach[i].r) si eventual mai mult
            if ( !dp[i - 1][j]  )
                continue;
            if ( s[i] - f[j + 1] > d )
                continue;

           int k = leftReach[i].r;
           if ( leftReach[i - 1].l <= j + 1 )
               k = max( k, rightReach[i - 1].r ); 

           dp[i][k] = true;
           last[i][k] = 'L';
        }
        // i merge la dreapta
        for ( int j = 0; j < m; j++ ) {
            if ( !dp[i - 1][j] )
                continue;

            int k = j;
            if ( rightReach[i].l <= j + 1 )
                k = rightReach[i].r;
            dp[i][k] = true;
            last[i][k] = 'R';
        }

        for ( int j = n - 1; j >= 0; j-- ) {
            dp[i][j] |= dp[i][j + 1];
            if ( dp[i][j + 1] ) 
                last[i][j] = last[i][j + 1];
        }

    }
    j = m;
    string sol = "";
    for ( int i = n; i >= 1; i-- ) {
        sol += last[i][j];
        if ( last[i][j] == 'R' ) 
            j = rightReach[i].l - 1;
        else 
            j = leftReach[i].l - 1;
    }
    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++ ) {
            for ( int j = 0; j <= m; j++ )
                printf( "%d", dp[i][j] );
            printf( "\n" );
        }
    #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: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47