Submission #1140536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140536		hashimali	Sprinklers (CEOI24_sprinklers)	C++20	3 / 100	2096 ms	10568 KiB

Main

#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];
void work(int mid){
    works=0;
    multiset<int>rem;
    for(int i=0;i<n;i++)
        d[i]=0;
    for(int i=0;i<m;i++)
        rem.insert(f[i]);
    for(int i=0;i<n;i++){
        if(rem.empty()){
            works=1;
            return;
        }
        int cur=*rem.begin();
        if(cur>=s[i])
            d[i]=1;
        else if(cur<(s[i]-mid)){
            works=0;
            return;
        }
        else if(cur>=(s[i]-mid))
            d[i]=0;
        else{
            auto up=rem.upper_bound(s[i]);
            if(up==rem.end())
                d[i]=0;
            else if(*up>=s[i+1])
                d[i]=0;
            else
                d[i]=1;
        }
        multiset<int>tmp;
        if(d[i]==0){
            //s[i]-mid....j....s[i]
            for(int j:rem)
                if((s[i]-mid)<=j and j<=s[i]){}
                else
                    tmp.insert(j);
        }
        if(d[i]==1){
            //s[i]....j....s[i]+mid
            for(int j:rem)
                if(s[i]<=j and j<=(s[i]+mid)){}
                else
                    tmp.insert(j);
        }
        rem=tmp;
    }
    works=(rem.empty());
}
void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>s[i];
    for(int i=0;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=0;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();
    }
}

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