Submission #1140559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140559		Sir_Ahmed_Imran	Sprinklers (CEOI24_sprinklers)	C++20	26 / 100	319 ms	3100 KiB

Main

                //    01001100 01001111 01010100 01000001    \\
                //                                           \\
                //                ╦  ╔═╗╔╦╗╔═╗               \\
                //                ║  ║ ║ ║ ╠═╣               \\
                //                ╩═╝╚═╝ ╩ ╩ ╩               \\
                //                                           \\
                //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;

#define N 100001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long

int dp[N];
int n, m;
vector<int> a, b;

void built(int x){
    int i, o, q;
    string s;
    i = n;
    while(i){
        o = b[dp[i - 1]], q = a[i - 1];
        if (o >= q - x && dp[i] == 1ll * (upper_bound(all(b), q) - b.begin())){
            s.append('L');
            i--;
        }
        else if (o >= q && dp[i] == 1ll * (upper_bound(all(b), q + x) - b.begin())){
            s.append('R');
            i--;
        }
        else{
            s.append('L');
            s.append('R');
            i -= 2;
        }
    }
    reverse(all(s));
    cout << s;
}

bool check(int x){
    int o, p, q;
    for (int i = 1; i <= n; i++){
        dp[i] = dp[i - 1], o = b[dp[i - 1]], q = a[i - 1];
        if (o >= q - x) dp[i] = max(dp[i], 1ll* (upper_bound(all(b), q) - b.begin()));
        if (o >= q) dp[i] = max(dp[i], 1ll* (upper_bound(all(b), q + x) - b.begin()));
        if (i > 1){
            o = b[dp[i - 2]], p = a[i - 2];
            if(o >= q - x && q - p < x) 
                dp[i] = max(dp[i], 1ll * (upper_bound(all(b), p + x) - b.begin()));
        }
    }
    return dp[n] == m;
}

void solve(){
    int o;
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> o;
        a.append(o); 
    }
    for (int i = 0; i < m; i++){
        cin >> o;
        b.append(o); 
    }
    if (n == 1 && b[0] < a[0] && a[0] < b[m - 1]){
        cout << "-1";
        return;
    }
    o = 0;
    b.append(1e17);
    for (int i = 536870912; i > 0; i /= 2)
        if (!check(o + i)) o += i;
    o++;
    check(o);
    cout << o << nl;
    built(o);
}

signed terminator(){
    L0TA;
    solve();
    return 0;
}

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