Submission #1094542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094542		epicci23	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	81 ms	4960 KiB

Main

#include <bits/stdc++.h>
using namespace std;
char ans[100010];
long long ss[100010],ff[100010],n,m,poz1,poz2;
bool verificare2(long long p)
{
    poz1=poz2=1;
    long long elim=-1;
    while(poz2<=m)
    {
        if(poz1>n)
            return false;
        if(ss[poz1]<=ff[poz2])
        {
            elim=ss[poz1]+p;
            ans[poz1-1]='R';
            ++poz1;
        }
        else
        {
            if(ss[poz1]-ff[poz2]>p)
                return false;
            ans[poz1-1]='L';
            elim=ss[poz1];
            if(poz1<n&&ss[poz1+1]-ff[poz2]<=p)
            {
                long long cop=poz2;
                while(cop<=m&&ff[cop]<=ss[poz1])
                    ++cop;
                if(cop<=m&&ff[cop]<ss[poz1+1])
                {
                    ans[poz1-1]='R';
                    ans[poz1]='L';
                    elim=ss[poz1]+p;
                    poz1+=2;
                }
                else
                    ++poz1;
            }
            else
                ++poz1;
        }
        while(poz2<=m&&elim>=ff[poz2])
            ++poz2;
    }
    return true;
}
long long s[100010],f[100010];
bool verificare(long long p)
{
    poz1=poz2=1;
    long long elim=-1;
    while(poz2<=m)
    {
        if(poz1>n)
            return false;
        if(s[poz1]<=f[poz2])
        {
            elim=s[poz1]+p;
            ans[poz1-1]='R';
            ++poz1;
        }
        else
        {
            if(s[poz1]-f[poz2]>p)
                return false;
            ans[poz1-1]='L';
            elim=s[poz1];
            if(poz1<n&&s[poz1+1]-f[poz2]<=p)
            {
                long long cop=poz2;
                while(cop<=m&&f[cop]<=s[poz1])
                    ++cop;
                if(cop<=m&&f[cop]<s[poz1+1])
                {
                    ans[poz1-1]='R';
                    ans[poz1]='L';
                    elim=s[poz1]+p;
                    poz1+=2;
                }
                else
                    ++poz1;
            }
            else
                ++poz1;
        }
        while(poz2<=m&&elim>=f[poz2])
            ++poz2;
    }
    return true;
}
int main()
{
    cin>>n>>m;
    for(long long i=1;i<=n;++i)
    {
        cin>>s[i];
        ss[i]=s[i];
        ans[i-1]='L';
        s[i]=1000000000-s[i];
    }
    for(long long i=1;i<=m;++i)
    {
        cin>>f[i];
        ff[i]=f[i];
        f[i]=1000000000-f[i];
    }
    sort(s+1,s+n+1);
    sort(f+1,f+m+1);
    if(n==1)
    {
        if(f[1]<s[1]&&s[1]<f[m])
        {
            cout<<-1;
            return 0;
        }
    }
    long long b=0,e=2000000000,mid;
    while(b<=e)
    {
        mid=(b+e)/2;
        if(verificare(mid)==true||verificare2(mid)==true)
            e=mid-1;
        else
            b=mid+1;
    }
    if(verificare2(b)==true)
    {
        cout<<b<<'\n'<<ans;
        return 0;
    }
    verificare(b);
    cout<<b<<'\n';
    for(int i=n-1;i>=0;--i)
        if(ans[i]=='R')
            cout<<'L';
        else
            cout<<'R';
    return 0;
}

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