Submission #1047095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047095		VahanAbraham	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	74 ms	7512 KiB

Main

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>

using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 200005;
const ll oo = 100000000000000000, MOD = 1000000007;

ll s[N], f[N], dp[N];
int n, m;
char pat[N], ans[N];

int func(int ind, ll l, ll r) {
    while (f[ind] >= l && f[ind] <= r && ind<=m) {
        ++ind;
    }
    --ind;
    return ind;
}

int func1(int ind, ll l, ll r,ll l1,ll r1) {
    while (ind<=m) {
        if ((f[ind] >= l && f[ind] <= r) || (f[ind] >= l1 && f[ind] <= r1)) {
            ++ind;
        }
        else {
            break;
        }
    }
    --ind;
    return ind;
}

bool from[N][5];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> f[i];
    }
    ll l = 0, r = 10000000000, anss = oo;
    while (l <= r) {
        ll mid = (l + r) / 2;
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = 0;
            for (int j = 0; j < 3; ++j) {
                from[i][j] = 0;
            }
        }
        for (int i = 0; i <= n-1; ++i) {
            int ind = dp[i];
            ++ind;
            ind = func(ind, s[i+1] - mid, s[i+1]);
            if (ind > dp[i + 1]) {
                dp[i + 1] = ind;
                for (int j = 0; j < 3; ++j) {
                    from[i + 1][j] = 0;
                }
                from[i + 1][0] = 1;
                ans[i + 1] = 'L';
            }
            ind = dp[i];
            ++ind;
            ind = func(ind, s[i+1], s[i+1] + mid);
            if (ind > dp[i + 1]) {
                dp[i + 1] = ind;
                for (int j = 0; j < 3; ++j) {
                    from[i + 1][j] = 0;
                }
                from[i + 1][1] = 1;
                ans[i + 1] = 'R';
            }
            ind = dp[i] + 1;
            ind = func1(ind, s[i+1], s[i+1] + mid, s[i + 2] - mid, s[i + 2]);
            if (ind > dp[i + 2]) {
                for (int j = 0; j < 3; ++j) {
                    from[i + 2][j] = 0;
                }
                from[i + 2][2] = 1;
                ans[i + 1] = 'R';
                dp[i + 2] = ind;
                ans[i + 2] = 'L';
            }
        }
        if (dp[n] == m) {
            for (int i = n; i >= 1; --i) {
                if (from[i][0] == 1) {
                    pat[i] = 'L';
                }
                else {
                    if (from[i][1] == 1) {
                        pat[i] = 'R';
                    }
                    else {
                        pat[i] = 'L';
                        pat[i - 1] = 'R';
                        --i;
                    }
                }
            }
            anss = min(anss, mid);
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    if (anss == oo) {
        cout << -1 << endl;
        return;
    }
    cout << anss << endl;
    for (int i = 1; i <= n; ++i) {
        cout << pat[i];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        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