제출 #1072646

#제출 시각아이디문제언어결과실행 시간메모리
1072646jer033Sprinklers (CEOI24_sprinklers)C++17
9 / 100
72 ms3256 KiB
#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++;
        }
        else
            cout << 'R';
    }
    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);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...