Submission #1369121

#TimeUsernameProblemLanguageResultExecution timeMemory
1369121888313666Sprinklers (CEOI24_sprinklers)C++20
3 / 100
117 ms5092 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define v vector
#define _ <<' '<<
#define print(x) cout<<#x<<": "<<(x)<<endl
int n,m;
v<int> a, b;


pair<bool, string> check(const int k) {
    v<int> dp(n+1, -1);
    v<string> prv(n+1, "");
    for (int i=0; i<n; i++) {
        if (i!=n-1) { // rl
            int ptr=dp[i];
            while (ptr!=m-1 && ((a[i+1]<=b[ptr+1] && b[ptr+1]<=a[i+1]+k)||(a[i+2]-k<=b[ptr+1] && b[ptr+1]<=a[i+2]))) ++ptr;
            dp[i+2]=ptr;
            prv[i+2]="LR"; // rev
        }
        int ptr=dp[i]; // l
        while (ptr!=m-1 && a[i+1]-k<=b[ptr+1] && b[ptr+1]<=a[i+1]) ++ptr;
        if (ptr>dp[i+1]) {
            dp[i+1]=ptr;
            prv[i+1]="L";
        }
        ptr=dp[i]; // r
        while (ptr!=m-1 && a[i+1]<=b[ptr+1] && b[ptr+1]<=a[i+1]+k) ++ptr;
        if (ptr>dp[i+1]) {
            dp[i+1]=ptr;
            prv[i+1]="R";
        }
    }
    string ret="";
    int cur=n;
    while (prv[cur]!="") {
        ret+=prv[cur];
        cur-=prv[cur].size();
    }
    reverse(ret.begin(), ret.end());
    return {dp[n]==m-1, ret};
}

int main(){
    cin>>n>>m;
    a.resize(n+1);
    b.resize(m);
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int i=0; i<m; i++) cin>>b[i];
    int lo=0, hi=1000000005, res=-1;
    string out;
    while (lo<=hi) {
        const auto m=lo+(hi-lo>>1);
        //print(m);
        auto [rs, st]=check(m);
        if (rs) {
            res=m;
            hi=m-1;
            out=st;
        } else lo=m+1;
    }
    cout<<res<<'\n';
    if (res!=-1) cout<<out<<'\n';
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...