Submission #1074922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074922		raphaelp	Sprinklers (CEOI24_sprinklers)	C++14	9 / 100	253 ms	9368 KiB

Main

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> &S, vector<int> &F, int K, vector<int> &ans)
{
    int N = S.size(), M = F.size();
    S.push_back(2000000001);
    ans.assign(N, 0);
    int buff = 0;
    bool b = 0;
    vector<int> next(N + 1), prev(N + 1), nextsprinkle(M + 1, N), after(N + 1);
    next[N] = M;
    prev[N] = M;
    after[N] = M;
    nextsprinkle[M] = N;
    for (int i = 0; i < N; i++)
    {
        while (buff < M && F[buff] < S[i])
        {
            nextsprinkle[buff] = i;
            buff++;
        }
        prev[i] = buff - 1;
        next[i] = buff;
    }
    buff = 0;
    for (int i = 0; i < N; i++)
    {
        while (buff < M && F[buff] - K <= S[i])
            buff++;
        after[i] = buff;
    }
    buff = 0;
    vector<int> sprinkle, done(M + 1);
    done[M] = 1;
    int cover = -1000000001;
    for (int i = 0; i < N; i++)
    {
        while (buff < M && F[buff] < S[i])
        {
            if (cover + K < F[buff])
                b = 0;
            else
                done[buff] = 1;
            buff++;
        }
        if (prev[i] == -1 || F[prev[i]] + K < S[i] || b == 1)
        {
            ans[i] = 1;
            sprinkle.push_back(S[i]);
            cover = S[i];
            b = 1;
        }
        if (next[i] == M || F[next[i]] - K > S[i])
        {
            ans[i] = -1;
            sprinkle.push_back(S[i] - K);
        }
        if (i > 0 && (prev[i] == -1 || S[i - 1] > F[prev[i]]))
        {
            ans[i] = 1;
            sprinkle.push_back(S[i]);
            cover = S[i];
            b = 1;
            ans[i - 1] = -1;
            sprinkle.push_back(S[i - 1] - K);
        }
    }
    while (buff < M)
    {
        if (cover + K < F[buff])
            b = 0;
        else
            done[buff] = 1;
        buff++;
    }
    buff = M - 1;
    b = 0;
    cover = 2000000001;
    for (int i = N - 1; i >= 0; i--)
    {
        while (buff >= 0 && F[buff] > S[i])
        {
            if (cover - K > F[buff])
                b = 0;
            else
                done[buff] = 1;
            buff--;
        }
        if (b == 1)
        {
            cover = S[i];
            sprinkle.push_back(S[i] - K);
            ans[i] = -1;
        }
        if (ans[i] == -1)
        {
            cover = S[i];
            b = 1;
        }
    }
    while (buff >= 0)
    {
        if (cover - K > F[buff])
            b = 0;
        else
            done[buff] = 1;
        buff--;
    }
    vector<pair<int, int>> dp(M);
    int donext = 0;
    for (int i = 0; i < M; i++)
    {
        if (done[i])
            continue;
        if (donext <= i)
        {
            dp[i].first = 1;
            donext = M + 10;
        }
        if (dp[i].first == 0)
            continue;
        if (S[nextsprinkle[i]] - K <= F[i])
        {
            if (done[next[nextsprinkle[i]]])
            {
                donext = next[nextsprinkle[i]];
            }
            dp[next[nextsprinkle[i]]].first = 1;
            if (S[nextsprinkle[i] + 1] - K <= F[i])
            {
                if (done[after[nextsprinkle[i]]])
                {
                    donext = after[nextsprinkle[i]];
                }
                dp[after[nextsprinkle[i]]].first = 1;
            }
        }
        if (dp[i].second == 1)
        {
            if (done[after[nextsprinkle[i] - 1]])
            {
                donext = after[nextsprinkle[i] - 1];
            }
            dp[after[nextsprinkle[i] - 1]].first = 1;
            if (F[after[nextsprinkle[i] - 1]] > S[nextsprinkle[i]])
                dp[after[nextsprinkle[i] - 1]].second = 1;
        }
    }
    S.pop_back();
    if (donext != M + 10)
        return 1;
    else
        return 0;
}
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> S(N), F(M), F2;
    for (int i = 0; i < N; i++)
    {
        cin >> S[i];
    }
    for (int i = 0; i < M; i++)
    {
        cin >> F[i];
    }
    int buff = 0;
    for (int i = 0; i < N; i++)
    {
        while (buff < M && F[buff] <= S[i])
        {
            if (F[buff] != S[i])
                F2.push_back(F[buff]);
            buff++;
        }
    }
    while (buff < M)
        F2.push_back(F[buff++]);
    swap(F, F2);
    if (N == 1 && F[0] < S[0] && F[M - 1] > S[0])
    {
        cout << -1;
        return 0;
    }
    int L = 0, R = 1000000000;
    vector<int> ans(N);
    while (L != R)
    {
        int m = (L + R) / 2;
        if (solve(S, F, m, ans))
            R = m;
        else
            L = m + 1;
    }
    bool b = solve(S, F, L, ans);
    cout << L << endl;
    for (int i = 0; i < N; i++)
        cout << ((ans[i] == 1) ? 'R' : 'L');
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:196:10: warning: unused variable 'b' [-Wunused-variable]
  196 |     bool b = solve(S, F, L, ans);
      |          ^

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