Submission #1293046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293046		dosts	Sprinklers (CEOI24_sprinklers)	C++20	20 / 100	2095 ms	3980 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);
    auto check =[&](int x,bool construct = 0) -> bool {
        vi dp(n+1,0);
        for (int i=1;i<=n;i++) {
            //bunu sola düz
            if (f[dp[i-1]+1] >= s[i]-x && f[dp[i-1]+1] <= s[i]) {
                int lst = dp[i-1];
                for (int j = dp[i-1]+1;j<=m;j++) {
                    if (s[i]-x <= f[j] && s[i] >= f[j]) {
                        lst = j;
                    }
                }
                if (lst > dp[i]) {
                    dp[i] = lst;
                    direction[i] = 'L';
                }
            }
            if (f[dp[i-1]+1] >= s[i]) {
                int lst = dp[i-1];
                for (int j = dp[i-1]+1;j<=m;j++) {
                    if (s[i] <= f[j] && s[i]+x >= f[j]) {
                        lst = j;
                    }
                }
                if (lst > dp[i]) {
                    dp[i] = lst;
                    direction[i] = 'R';
                }
            }
            if (i>1 && s[i]-x <= s[i-1] && f[dp[i-2]+1] <= s[i] && f[dp[i-2]+1] >= s[i]-x) {
                int lst = dp[i-2];
                for (int j = dp[i-2]+1;j<=m;j++) {
                    if (s[i]-x <= f[j] && s[i] >= f[j]) {
                        lst = j;
                    }
                    if (s[i-1]+x >= f[j] && s[i-1] <= f[j]) {
                        lst = j;
                    }
                }
                if (lst > dp[i]) {
                    dp[i] = lst;
                    direction[i] = 'L';
                    direction[i-1] = 'R';
                }
            }
            if (dp[i] == m) {
                for (int j = i+1;j<=n;j++) direction[j] = 'R';
                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,1);
        for (int i=1;i<=n;i++) cout << direction[i];
        cout << '\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: 0 / 6
• Subtask 3: 17 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47