Submission #1293082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293082		dosts	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	111 ms	8096 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e18;

const int N = 1e5+1;

void solve() {
    int n,m;
    cin >> n >> m;
    vi s(n+1),f(m+1);
    for (int i=1;i<=n;i++) cin >> s[i];
    for (int i=1;i<=m;i++) cin >> f[i];
    vector<char> direction(n+1,'R');
    vi action(n+1);
    auto check =[&](int x) -> bool {
        action.assign(n+1,1);
        vi dp(n+1,0);
        int ptr = 0,ptr2 = 0,ptr3 = 0;
        for (int i=1;i<=n;i++) {
            while (ptr<m && f[ptr+1] <= s[i]) ptr++;
            while (ptr2<m && f[ptr2+1] <= s[i]+x) ptr2++;
            while (i>1 && ptr3 < m && f[ptr3+1] <= s[i-1]+x) ptr3++;
            dp[i] = dp[i-1];
            if (f[dp[i-1]+1] < s[i]-x) return false;
            //bunu sola düz
            if (f[dp[i-1]+1] <= s[i]) {
                if (ptr > dp[i]) {
                    dp[i] = ptr;
                    action[i] = 1;
                }
            }
            if (f[dp[i-1]+1] >= s[i]) {
                if (ptr2 > dp[i]) {
                    dp[i] = ptr2;
                    action[i] = 2;
                }
            }
            if (i>1 && (s[i-1]+x >= s[i]-x) && (f[dp[i-2]+1] <= s[i] && f[dp[i-2]+1] >= s[i]-x)) {
                if (ptr3 > dp[i]) {
                    dp[i] = ptr3;
                    action[i] = 3;
                }
            }
            if (dp[i] == m) return true;
        }
        return false;
    };

    int l = 0;
    int r = inf;
    while (l<=r) {
        int mid = (l+r) >> 1;
        if (check(mid)) r = mid-1;
        else l = mid+1;
    }
    if (l < inf) {
        cout << l << '\n';
        check(l);
        string ans;
        int curr = n;
        while (curr >= 1) {
            if (action[curr] == 1) {
                ans+='L';
                curr--;
            }
            else if (action[curr] == 2) {
                ans+='R';
                curr--;
            }
            else {
                ans+="LR";
                curr-=2;
            }
        }
        reverse(all(ans));
        cout << ans << '\n';
    }
    else cout << -1 << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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