Submission #1232014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232014		PVM_pvm	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	88 ms	1508 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)
{
    int len=1<<n;
    for (int msk=0;msk<len;msk++)
    {
        bool dl=true;
        for (int q=1;q<=m;q++)
        {
            bool mg=false;
            for (int w=1;w<=n;w++)
            {
                if ((msk>>(w-1))%2==0 && f[q]<=s[w])
                {
                    if ((s[w]-f[q])<=k) {mg=true;break;}
                }
                if ((msk>>(w-1))%2==1 && f[q]>=s[w])
                {
                    if ((f[q]-s[w])<=k) {mg=true;break;}
                }
            }
            if (!mg)
            {
                dl=false;
                break;
            }
        }
        if (dl)
        {
            if (otp)
            {
                for (int w=0;w<n;w++)
                {
                    if ((msk>>w)%2==0) otg[w]='L';
                    else otg[w]='R';
                }
                cout<<otg<<"\n";
            }
            return true;
        }
    }
    return false;
}
bool check2(int k, bool otp)
{
    int lstS=n,lstF=m;
    while (true)
    {
        if (lstF<=0) break;
        if (lstS<=0) return false;
        //cout<<lstS<<" "<<lstF<<"\n";
        if (f[lstF]>s[lstS])
        {
            ///nqkoi trqbva da prysne lstF
            int l=0,r=lstS+1;
            while (l<r-1)
            {
                int mid=(l+r)/2;
                if (s[mid]<(f[lstF]-k)) l=mid;
                else r=mid;
            }
            if (r==(lstS+1)) return false;
            ///r e posledniq koito ima umeniqta mi
            ///sega tyrsim pyrvoto cvete, koeto e po-golqmo ili ravno na r
            int ll=0,rr=lstF;
            while (ll<rr-1)
            {
                int mid=(ll+rr)/2;
                if (f[mid]>=s[r]) rr=mid;
                else ll=mid;
            }
            ///rr e pyrvoto cvete, koeto shte byde hvanato v struqta
            ///sega tyrsim pyrviq, koito e po-malko ili ravno na rr
            int lll=r,rrr=lstS+1;
            while (lll<rrr-1)
            {
                int mid=(lll+rrr)/2;
                if (s[mid]<=f[rr]) lll=mid;
                else rrr=mid;
            }
            ///lll e tozi koito trqbva da ocveti lstF
            otg[lll-1]='R';
            int mnn=s[lll];
            if (lll!=lstS)
            {
                for (int q=lll+1;q<=lstS;q++)
                {
                    mnn=min(mnn,s[q]-k);
                    otg[q-1]='L';
                }
            }
            lstS=lll-1;
            while (lstF>=1 && f[lstF]>=mnn) lstF--;
        }
        else
        {
            ///lstS pryska nalqvo
            otg[lstS-1]='L';
            while (lstF>=1 && (s[lstS]-f[lstF])<=k) lstF--;
            lstS--;
        }
    }
    if (otp)
    {
        for (int q=0;q<lstS;q++) otg[q]='L';
        cout<<otg<<"\n";
    }
    return true;
}

int main()
{
    otg="";
    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;
        //cout<<mid<<"\n";
        bool ch=check2(mid,0);
        if (ch) r=mid;
        else l=mid;
    }
    if (r==(1e9+1)) cout<<"-1\n";
    else
    {
        cout<<r<<"\n";
        check2(r,1);
    }
}
/*
3 4
10 18 20
10 11 14 24
*/

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