Submission #1072866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072866		jer033	Sprinklers (CEOI24_sprinklers)	C++17	3 / 100	26 ms	832 KiB

Main

#include <bits/stdc++.h>
using namespace std;

vector<int> in_between;

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

            while ((towater<M) and (flowers[towater]<=covered))
                towater++;
        }
        i++;
    }
    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;
    int i = 0;
    while (i<N)
    {
        if (towater<M)
        {
            int loc = sprinks[i];
            if (flowers[towater]<loc)
            {
                if (((i+2)<N) and (flowers[towater] >= (sprinks[i+2]-K)))
                {
                    i+=2;
                    covered = sprinks[i+2]+K;
                    cout << "RLR";
                }
                else if (((i+1)<N) and (flowers[towater] >= (sprinks[i+1]-K)) and (in_between[i]>0))
                {
                    i++;
                    covered = loc+K;
                    cout << "RL";
                }
                else
                {
                    covered = loc;
                    cout << 'L';
                }
            }
            else
            {
                covered = loc+K;
                cout << 'R';
            }
 
            while ((towater<M) and (flowers[towater]<=covered))
                towater++;
        }
        else
            cout << 'R';
        i++;
    }
    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];
    sort(flowers.begin(), flowers.end());
    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
    {
        in_between = vector<int> (N-1, 0);
        int curr = 0;
        for (int i=0; i<M; i++)
        {
            while (((curr+1)<N) and (flowers[i]>=sprinks[curr+1]))
                curr++;
            if (((curr+1)<N) and (flowers[i]>sprinks[curr]) and (flowers[i]<sprinks[curr+1]))
                in_between[curr]++;
        }

        /*bool tapos = 0;
        for (int guess = 0; guess<=8; guess++)
        {
            if ((!tapos) and possible(guess, sprinks, flowers))
            {
                report(guess, sprinks, flowers);
                tapos = 1;
            }
        }*/
        //for (int i=0; i<(N-1); i++)
            //cout << in_between[i] << '\n';

        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
• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47