oj.uz

Submission #1118450

# Submission time Handle Problem Language Result Execution time Memory
1118450 2024-11-25T13:55:55 Z Tenis0206 Sprinklers (CEOI24_sprinklers) C++11
3 / 100
 2000 ms 928 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)
{
    int nr = 0;
    for(int i=1;i<=m;i++)
    {
        if(f[i] >= l && f[i] <= r)
        {
            ++nr;
        }
    }
    return nr;
    /*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)
{
    for(int i=1;i<=n;i++)
    {
        if(s[i] >= val)
        {
            return i;
        }
    }
    /*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]);
}

signed 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;
}

Compilation message

Main.cpp: In function 'int search_last(int)':
Main.cpp:98:1: warning: control reaches end of non-void function [-Wreturn-type]
   98 | }
      | ^

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 10 ms 604 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 22 ms 860 KB Correct
5 Correct 11 ms 860 KB Correct
6 Correct 1 ms 348 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 5 ms 504 KB Correct
9 Correct 1 ms 348 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Execution timed out 2058 ms 860 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 1 ms 348 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 1 ms 512 KB Correct
5 Incorrect 1 ms 348 KB User solution is incorrect
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Execution timed out 2060 ms 928 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 1 ms 348 KB Correct
3 Correct 10 ms 604 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 22 ms 860 KB Correct
6 Correct 11 ms 860 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 1 ms 348 KB Correct
9 Correct 5 ms 504 KB Correct
10 Correct 1 ms 348 KB Correct
11 Execution timed out 2058 ms 860 KB Time limit exceeded
12 Halted 0 ms 0 KB -