Submission #1293049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293049		dosts	Sprinklers (CEOI24_sprinklers)	C++20	26 / 100	110 ms	8092 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 {
        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++;
            //bunu sola düz
            if (f[dp[i-1]+1] >= s[i]-x && f[dp[i-1]+1] <= s[i]) {
                if (ptr > dp[i]) {
                    dp[i] = ptr;
                    direction[i] = 'L';
                }
            }
            if (f[dp[i-1]+1] >= s[i]) {
                if (ptr2 > dp[i]) {
                    dp[i] = ptr2;
                    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) {
                if (ptr3 > dp[i]) {
                    dp[i] = ptr3;
                    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);
        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: 6 / 6
• Subtask 3: 17 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47