Submission #1140716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140716		Ghulam_Junaid	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	145 ms	16428 KiB

Main

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

typedef long long ll;

const ll N = 2e5 + 100;
ll n, m, a[N], f[N], dp[N], par[N];
string used[N];
vector<pair<ll, ll>> vec;

void work(ll p){
    memset(dp, 0, sizeof dp);

    dp[vec.size()] = 1;
    vector<ll> si;
    for (ll i = vec.size() - 1; i >= 0; i --){
        if (vec[i].second == 1){
            if (si.empty()) dp[i] = 0;
            else{
                ll last = si.back();
                if (dp[last + 1] and ((vec[last].first - p) <= vec[i].first)){
                    dp[i] = 1;
                    par[i] = last + 1;
                    used[i] = "L";
                    continue;
                }

                if (si.size() > 1){
                    ll last2 = si[si.size() - 2];
                    bool good = ((vec[last2].first - p) <= vec[i].first);
                    
                    if (si.size() > 2 and vec[si[si.size() - 3]].first <= vec[last].first + p){
                        if (good and dp[si[si.size() - 3]]){
                            dp[i] = 1;
                            par[i] = si[si.size() - 3];
                            used[i] = "RL";
                        }
                    }
                    else{
                        ll nxt = upper_bound(vec.begin(), vec.end(), (pair<ll, ll>) {vec[last].first + p, 2}) - vec.begin();
                        if (good and dp[nxt]){
                            dp[i] = 1;
                            par[i] = nxt;
                            used[i] = "RL";
                        }
                    }

                }
            }
        }
        else{
            if (si.size() and vec[si.back()].first <= vec[i].first + p){
                if (dp[si.back()]){
                    dp[i] = 1;
                    par[i] = si.back();
                    used[i] = "R";
                }
            }
            else{
                ll nxt = upper_bound(vec.begin(), vec.end(), (pair<ll, ll>) {vec[i].first + p, 2}) - vec.begin();
                if (dp[nxt]){
                    dp[i] = 1;
                    par[i] = nxt;
                    used[i] = "R";
                }
            }
            si.push_back(i);
        }
    }
}

int main(){
    cin >> n >> m;
    for (ll i = 0; i < n; i ++){
        cin >> a[i];
        vec.push_back({a[i], 0});
    }
    for (ll i = 0; i < m; i ++){
        cin >> f[i];
        vec.push_back({f[i], 1});
    }
    sort(vec.begin(), vec.end());

    if (n == 1){
        ll mn = f[0];
        ll mx = f[m - 1];
        if (mn < a[0] and a[0] < mx)
            cout << -1 << endl;
        else{
            if (mx <= a[0]){
                cout << a[0] - mn << endl;
                cout << "L" << endl;
            }
            else{
                cout << mx - a[0] << endl;
                cout << "R" << endl;
            }
        }
        return 0;
    }

    ll l = -1;
    ll r = 1e9;
    for (ll i = 0; i < 10; i ++){
        work(i);
        if (dp[0]){
            l = i - 1;
            r = i;
            break;
        }
    }
    while (r - l > 1){
        ll p = (l + r) / 2;
        work(p);
        
        if (dp[0]) r = p;
        else l = p;
    }

    work(r);
    cout << r << endl;
    ll cur = 0;
    string res;
    while (cur < vec.size()){
        res += used[cur];
        cur = par[cur];
    }
    if (res.size() != n){
        cout << 1 / 0 << endl;
    }
    cout << res << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:129:19: warning: division by zero [-Wdiv-by-zero]
  129 |         cout << 1 / 0 << endl;
      |                 ~~^~~

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