Submission #1118445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118445		Tenis0206	Sprinklers (CEOI24_sprinklers)	C++11	9 / 100	204 ms	6124 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;

int n,m;
int s[nmax + 5], f[nmax + 5];

int dp[nmax + 5];

char dir[nmax + 5], dirm[nmax + 5];
int l[nmax + 5];

char r[nmax + 5];

int count_flowers(int l, int r)
{
    if(l > r)
    {
        return 0;
    }
    int st = 1;
    int dr = m;
    int poz_l = 0, poz_r = 0;
    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(f[mij] >= l)
        {
            poz_l = mij;
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    st = 1;
    dr = m;
    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(f[mij] <= r)
        {
            poz_r = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    if(poz_l == 0 || poz_r == 0)
    {
        return 0;
    }
    return (poz_r - poz_l + 1);
}

int search_last(int val)
{
    int st = 1;
    int dr = n;
    int poz = 0;
    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(s[mij] >= val)
        {
            poz = mij;
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    return poz;
}

bool ok(int k)
{
    dp[0] = -1;
    for(int i=1;i<=n;i++)
    {
        if(count_flowers(dp[i - 1] + 1, s[i] - 1) == 0)
        {
            dp[i] = s[i] + k;
            dir[i] = 'R';
            l[i] = i;
            continue;
        }
        dir[i] = 'L';
        int poz = search_last(s[i] - k);
        l[i] = poz;
        if(poz == i)
        {
            if(count_flowers(dp[i - 1] + 1, s[i] - k - 1) == 0)
            {
                dp[i] = s[i];
            }
            else
            {
                dp[i] = -1;
            }
        }
        else if(poz == i - 1)
        {
            if(count_flowers(dp[i - 2] + 1, s[i] - k - 1) == 0)
            {
                dirm[i] = 'R';
                dp[i] = s[i - 1] + k;
            }
            else if(count_flowers(dp[i - 2] + 1, s[i - 1] - k - 1) == 0)
            {
                dirm[i] = 'L';
                dp[i] = s[i];
            }
            else
            {
                dp[i] = -1;
            }
        }
        else
        {
            if(count_flowers(dp[poz - 1] + 1, s[poz] - k - 1) == 0)
            {
                dp[i] = s[i - 1] + k;
            }
            else
            {
                dp[i] = -1;
            }
        }
    }
    return (dp[n] >= f[m]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>f[i];
    }
    int st = 0;
    int dr = 1e9;
    int rez = -1;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        if(ok(mij))
        {
            rez = mij;
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    cout<<rez<<'\n';
    if(rez == -1)
    {
        return 0;
    }
    ok(rez);
    for(int i=1;i<=n;i++)
    {
        if(l[i] == 0)
        {
            while(true);
        }
    }
    int poz = n;
    while(poz >= 1)
    {
        r[poz] = dir[poz];
        if(l[poz] == poz - 1)
        {
            r[poz - 1] = dirm[poz];
        }
        else
        {
            for(int j=poz-1;j>=l[poz];j++)
            {
                r[j] = 'L';
            }
        }
        poz = l[poz] - 1;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<r[i];
    }
    cout<<'\n';
    return 0;
}

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