oj.uz

Submission #1118441

# Submission time Handle Problem Language Result Execution time Memory
1118441 2024-11-25T13:44:26 Z Tenis0206 Sprinklers (CEOI24_sprinklers) C++11
9 / 100
 204 ms 5956 KB 
#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);
    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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 7 ms 1616 KB Correct
3 Correct 1 ms 508 KB Correct
4 Correct 8 ms 1788 KB Correct
5 Correct 14 ms 1616 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 4 ms 592 KB Correct
9 Correct 1 ms 336 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 10 ms 1616 KB Correct
3 Correct 7 ms 592 KB Correct
4 Correct 90 ms 4060 KB Correct
5 Correct 63 ms 4064 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 96 ms 4080 KB Correct
9 Correct 183 ms 4180 KB Correct
10 Correct 27 ms 4176 KB Correct
11 Correct 38 ms 2712 KB Correct
12 Correct 42 ms 2396 KB Correct
13 Correct 53 ms 3084 KB Correct
14 Correct 93 ms 3352 KB Correct
15 Correct 70 ms 3420 KB Correct
16 Correct 53 ms 2988 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 1 ms 472 KB Correct
5 Runtime error 6 ms 4176 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 46 ms 1924 KB Correct
3 Correct 176 ms 4168 KB Correct
4 Correct 203 ms 4168 KB Correct
5 Correct 202 ms 4148 KB Correct
6 Correct 187 ms 4148 KB Correct
7 Correct 204 ms 4156 KB Correct
8 Runtime error 192 ms 5956 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Correct 7 ms 1616 KB Correct
4 Correct 1 ms 508 KB Correct
5 Correct 8 ms 1788 KB Correct
6 Correct 14 ms 1616 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 1 ms 336 KB Correct
9 Correct 4 ms 592 KB Correct
10 Correct 1 ms 336 KB Correct
11 Correct 10 ms 1616 KB Correct
12 Correct 7 ms 592 KB Correct
13 Correct 90 ms 4060 KB Correct
14 Correct 63 ms 4064 KB Correct
15 Correct 1 ms 336 KB Correct
16 Correct 1 ms 336 KB Correct
17 Correct 96 ms 4080 KB Correct
18 Correct 183 ms 4180 KB Correct
19 Correct 27 ms 4176 KB Correct
20 Correct 38 ms 2712 KB Correct
21 Correct 42 ms 2396 KB Correct
22 Correct 53 ms 3084 KB Correct
23 Correct 93 ms 3352 KB Correct
24 Correct 70 ms 3420 KB Correct
25 Correct 53 ms 2988 KB Correct
26 Correct 1 ms 336 KB Correct
27 Correct 1 ms 472 KB Correct
28 Runtime error 6 ms 4176 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -