Submission #1178595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178595		alexdd	Sprinklers (CEOI24_sprinklers)	C++20	3 / 100	2097 ms	13268 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 4e9;
int n,m;
int s[100005],f[100005];
bool broken[100005];
char dir[100005];
map<int,int> mp;
bool verif(int k)
{
    vector<bool> used(n+2,0);
    int ps=1,pf=1;
    while(ps<=n || pf<=m)
    {
        if(ps<=n && (pf>m || s[ps] < f[pf]))
        {
            if(!used[ps])
            {
                dir[ps] = 'R';
                while(pf<=m && f[pf] <= s[ps] + k)
                    pf++;
            }
            ps++;
        }
        else
        {
            if(ps>n || f[pf] < s[ps] - k)
                return 0;
            int cur = ps;
            while(!broken[cur] && cur+1<=n && f[pf] >= s[cur+1] - k)
            {
                cur++;
            }
            assert(used[cur] == 0);
            used[cur] = 1;
            dir[cur] = 'L';
            while(pf<=m && f[pf] <= s[cur])
                pf++;
        }
    }
    return 1;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        mp[s[i]]++;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>f[i];
        if(mp[f[i]])
        {
            i--;
            m--;
        }
    }
    for(int i=1;i<n;i++)
    {
        broken[i] = 1;
        for(int j=1;j<=m;j++)
        {
            if(s[i] < f[j] && f[j] < s[i+1])
            {
                broken[i] = 0;
                break;
            }
        }
    }
    if(!verif(INF))
    {
        cout<<-1;
        return 0;
    }
    int st=0,dr=INF,ans=INF;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(verif(mij))
        {
            ans = mij;
            dr = mij-1;
        }
        else
            st = mij+1;
    }
    verif(ans);
    cout<<ans<<"\n";
    for(int i=1;i<=n;i++)
        cout<<dir[i];
    return 0;
}

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