제출 #1140598

#제출 시각아이디문제언어결과실행 시간메모리
1140598hashimaliSprinklers (CEOI24_sprinklers)C++20
0 / 100
51 ms1352 KiB
#include <bits/stdc++.h>
#define endl '\n'
#define ld long double
#define pb push_back
#define pf push_front
#define mod 998244353
#define se second
#define fi first
#define all(ls) (ls).begin(),(ls).end()
#define int long long
using namespace std;
int n,m,works;
const int N=1e5+10;
int s[N],f[N],d[N],dp[N];
pair<int,int>nxt(int x){
    return {lower_bound(f+1,f+n+1,x)-f,upper_bound(f+1,f+n+1,x)-f-1};
}
void work(int mid){
    works=0;
    for(int i=1;i<=n;i++)
        dp[i]=0;
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1];
        pair<int,int>a=nxt(s[i]-mid),b=nxt(s[i]),c=nxt(s[i]+mid);
        if((dp[i-1]+1)>=a.fi and dp[i]<b.se){
            d[i]=0;
            dp[i]=b.se;
        }
        if((dp[i-1]+1)>=b.fi and dp[i]<c.se){
            d[i]=1;
            dp[i]=c.se;
        }
        if(i>1){
            pair<int,int>D=nxt(s[i-1]+mid);
            if((dp[i-2]+1)>=a.fi and dp[i]<D.se){
                d[i]=0;
                d[i-1]=1;
                dp[i]=D.se;
            }
        }
    }
    works=(dp[n]==m);
}
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];
    int low=0,high=1e14;
    while(low<=high){
        int mid=(low+high)/2;
        work(mid);
        if(works)
            high=mid-1;
        else
            low=mid+1;
    }
    if(low==(1e14+1))
        low=-1;
    cout<<low<<endl;
    if(low!=-1){
        work(low);
        for(int i=1;i<=n;i++){
            if(d[i]==0)
                cout<<'L';
            else
                cout<<'R'; 
        }
        cout<<endl;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    for(int i=1;i<=t;i++){
        // cout<<"Scenario #"<<i<<":"<<" ";
        solve();
    }
}
#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...