제출 #1232195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232195		alexander707070	Sprinklers (CEOI24_sprinklers)	C++20	6 / 100	44 ms	2888 KiB

Main

#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;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47