Submission #1075626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075626		abouton	Sprinklers (CEOI24_sprinklers)	C++17	3 / 100	96 ms	3364 KiB

Main

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

int S, F;
int kMin, kMax;
vector<int> sprink;
vector<int> fleurs;
int dernier; 
deque<int> poss;
int possibleS[100000+42];
int possibleF[100000+42];
bool directions[100000+42];
int parQui[100000+42];
int parQuiMin[100000+42];

int val(int a, int b)
{
    if (!b) return fleurs[a];
    return sprink[a];
}

struct objet
{
    int pos;
    int typ;
    bool operator<(const objet &autre) const
    {
        if (val(pos,typ) == val(autre.pos, autre.typ)) return typ < autre.typ;
        return val(pos,typ) < val(autre.pos, autre.typ);
    }
};
vector<objet> fusion;

bool tester(int k)
{
    for (int i = 0; i < F; i ++)
    {
        parQui[i] = -1;
    }
    for (int i = 0; i < S; i ++)
    {
        possibleS[i] = 0;
    }
    for (int i = 0; i < F; i ++)
    {
        possibleF[i] = 0;
    }
    dernier=-1;
    poss.clear();
    for (int i = fusion.size()-1; i >=0; i --)
    {
        int endr = val(fusion[i].pos, fusion[i].typ);

        int sorte = fusion[i].typ;
        int ind = fusion[i].pos;
        if (sorte == 1)
        {
            auto ans = upper_bound(fleurs.begin(), fleurs.end(), endr + k);
            if (ans == fleurs.end())
            {   
                possibleS[fusion[i].pos] = true;
            }
            else if (sprink[ind+1] <= fleurs[ans-fleurs.begin()])
            {
                possibleS[ind] = possibleS[ind+1];
            }
            else
            {
                possibleS[fusion[i].pos] = possibleF[ans - fleurs.begin()];
            }
            if (ind != S-1 && sprink[ind+1] <= sprink[ind]+k)
            {
                poss.push_back(ind+1);
            }
            dernier = fusion[i].pos;
        }

        if (sorte == 0)
        {
            while (!poss.empty() && sprink[poss.front()] > endr + k)
            {
                poss.pop_front();
            }
            if (dernier != -1)
            {
                if (sprink[dernier] <= endr+k)
                {
                    auto ans = upper_bound(fleurs.begin(), fleurs.end(), sprink[dernier]);
                    if (ans == fleurs.end() || possibleF[ans-fleurs.begin()])
                    {
                        possibleF[ind] = true;
                        parQui[ind] = dernier;
                    }
                }
            }
            if (!poss.empty())
            {
                possibleF[ind]= possibleS[poss[0]];
                if (possibleF[ind]) parQui[ind] = poss[0];
            }
        }
    }
    if (fusion[0].typ == 0) return possibleF[0];
    return possibleS[0];
}

int main()
{
    cin >> S >> F;
    sprink.resize(S);
    fleurs.resize(F);
    fusion.resize(S+F);
    for (int i = 0; i < S; i ++) {cin >> sprink[i]; fusion[i] = {i,1};}
    int position = 0;
    int vF=F;
    for (int i = 0; i <vF; i ++)
    {
        cin >> fleurs[position];
        auto dans = lower_bound(sprink.begin(), sprink.end(), fleurs[position]);
        if ((dans == sprink.end() || *dans != fleurs[position]) && (position == 0 || fleurs[position] != fleurs[position-1])) 
        {
            fusion[position+S]={position, 0};
            position++;
        }
        else F--;
    }
    fusion.resize(S+F);
    fleurs.resize(F);
    sort(fusion.begin(), fusion.end());
    kMin = 0;
    kMax = 1e9+10;
    while (kMin < kMax)
    {
        int k = kMin + (kMax-kMin)/2;
        if (tester(k))
        {
            kMax = k;
            for (int i = 0; i < F; i ++) parQuiMin[i] = parQui[i];
        }
        else
        {
            kMin = k+1;
        }
    }
    if (kMin> 1e9)
    {
        cout << "-1\n";
        return 0;
    }
    cout << kMin << "\n";
    for (int i = 0; i < S; i ++)
    {
        directions[parQuiMin[i]] = 1;
    }
    for (int i = 0; i < S; i ++)
    {
        directions[i] ? cout << 'L' : cout << 'R';
    }
    cout << '\n';
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47