제출 #1072645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072645		jer033	Sprinklers (CEOI24_sprinklers)	C++17	3 / 100	25 ms	856 KiB

Main

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