Submission #1231917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231917		PVM_pvm	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	78 ms	2256 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
int n,m;
int s[MAXN];
int f[MAXN];
string otg="";
bool check(int k, bool otp)
{
    vector<int> pos;
    for (int q=1;q<=m;q++) pos.push_back(f[q]);
    for (int q=n;q>=1;q--)
    {
        if (pos.empty())
        {
            otg[q-1]='R';
            continue;
        }
        if (pos[ pos.size()-1 ]>s[q])
        {
            ///strelqme nadqsno
            otg[q-1]='R';
            if ( (pos[pos.size()-1]-s[q])>k ) return false;
            while (!pos.empty() && pos[ pos.size()-1 ]>=s[q]) pos.pop_back();
        }
        else
        {
            ///strelqme nalqvo
            otg[q-1]='L';
            while (!pos.empty() && (s[q]-pos[ pos.size()-1 ])<=k) pos.pop_back();
        }
    }
    if (!pos.empty()) return false;
    if (otp) cout<<otg<<"\n";
    return true;
}
int main()
{
    cin>>n>>m;
    for (int q=0;q<n;q++) otg+='.';
    for (int q=1;q<=n;q++) cin>>s[q];
    for (int q=1;q<=m;q++) cin>>f[q];
    int l=-1,r=1e9+1;
    while (l<r-1)
    {
        int mid=(l+r)/2;
        bool ch=check(mid,0);
        if (ch) r=mid;
        else l=mid;
    }
    if (r==(1e9+1)) cout<<"-1\n";
    else
    {
        cout<<r<<"\n";
        check(r,1);
    }
}

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