oj.uz

Submission #1072645

# Submission time Handle Problem Language Result Execution time Memory
1072645 2024-08-24T01:33:47 Z jer033 Sprinklers (CEOI24_sprinklers) C++17
3 / 100
 25 ms 856 KB 
#include <bits/stdc++.h>
using namespace std;

bool possible(int K, vector<int> (&sprinks), vector<int> (&flowers))
{
    int N = sprinks.size();
    int M = flowers.size();
    int covered = -1;
    int towater = 0;
    for (int i=0; i<N; i++)
    {
        if (towater<M)
        {
            int loc = sprinks[i];
            if (flowers[towater]<loc)
            {
                covered = loc;
                if (flowers[towater] < (loc-K))
                    return 0;
            }
            else
                covered = loc+K;

            while ((towater<M) and (flowers[towater]<=covered))
                towater++;
        }
    }
    if (towater==M)
        return 1;
    return 0;
}

void report(int K, vector<int> (&sprinks), vector<int> (&flowers))
{
    cout << K << '\n';
    int N = sprinks.size();
    int M = flowers.size();
    int covered = -1;
    int towater = 0;
    for (int i=0; i<N; i++)
    {
        if (towater<M)
        {
            int loc = sprinks[i];
            if (flowers[towater]<loc)
            {
                covered = loc;
                cout << 'L';
            }
            else
            {
                covered = loc+K;
                cout << 'R';
            }

            while ((towater<M) and (flowers[towater]<=covered))
                towater++;
        }
    }
    cout << '\n';
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> sprinks(N);
    vector<int> flowers(M);
    for (int i=0; i<N; i++)
        cin >> sprinks[i];
    for (int i=0; i<M; i++)
        cin >> flowers[i];
    if (N==1)
    {
        int left = flowers[0]-sprinks[0];
        int righ = flowers[M-1]-sprinks[0];
        if ((left<0) and (righ>0))
            cout << "-1\n";
        else
        {
            cout << max(abs(left), abs(righ)) << '\n';
            if (left<0)
                cout << "L\n";
            else
                cout << "R\n";
        }
    }
    else
    {
        int lo = 0;
        int hi = 1'000'000'005;
        while (lo!=hi)
        {
            int mid = (lo+hi)/2;
            if (possible(mid, sprinks, flowers))
                hi = mid;
            else
                lo = mid+1;
        }
        report(lo, sprinks, flowers);
    }
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect string length
2 Halted 0 ms 0 KB -

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 21 ms 856 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 24 ms 832 KB Correct
5 Correct 25 ms 604 KB Correct
6 Correct 0 ms 344 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 5 ms 508 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect string length
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect string length
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect string length
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect string length
2 Halted 0 ms 0 KB -