Submission #1231936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231936		PVM_pvm	Sprinklers (CEOI24_sprinklers)	C++20	20 / 100	2097 ms	840 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)
{
    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]='L';
            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);
    }
}
/*
3 4
10 18 20
10 11 14 24
*/

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