Submission #1232195

#TimeUsernameProblemLanguageResultExecution timeMemory
1232195alexander707070Sprinklers (CEOI24_sprinklers)C++20
6 / 100
44 ms2888 KiB
#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

const int inf=1e9+7;

int n,m;

struct item{
    int pos,type,id;

    inline friend bool operator < (item fr,item sc){
        if(fr.pos!=sc.pos)return fr.pos<sc.pos;
        return fr.type<sc.type;
    }
}s[MAXN];

int ans;
char sol[MAXN];

bool ok(int len){
    int to=-1,last=-1;

    for(int i=1;i<=n+m;i++){

        if(s[i].type==2){
            if(s[i].pos<=to)continue;
            else if(last==-1)last=s[i].pos;
        }else{
            if(last==-1){
                sol[s[i].id]='R';
                to=s[i].pos+len;
            }else{
                if(last<s[i].pos-len)return false;
                sol[s[i].id]='L'; last=-1;
            }
        }
    }

    return last==-1;
}

int bin(){
    int l=-1,r=inf,tt;

    while(l+1<r){
        tt=(l+r)/2;

        if(ok(tt)){
            r=tt;
        }else{
            l=tt;
        }
    }

    return r;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    for(int i=1;i<=n;i++){
        cin>>s[i].pos;
        s[i].type=1;
        s[i].id=i;
    }

    for(int i=1;i<=m;i++){
        cin>>s[n+i].pos;
        s[n+i].type=2;
    }

    sort(s+1,s+n+m+1);

    ans=bin();
    if(ans==inf){
        cout<<"-1\n";
    }else{
        ok(ans);
        cout<<ans<<"\n";
        for(int i=1;i<=n;i++)cout<<sol[i];
        cout<<"\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...