Submission #1074978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074978		raphaelp	Sprinklers (CEOI24_sprinklers)	C++14	9 / 100	2017 ms	15092 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);
    F.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 + 1);
    vector<pair<vector<pair<int, int>>, vector<pair<int, int>>>> changes(M + 1);
    vector<pair<int, int>> dp2(M + 1);
    int donext = 0;
    for (int i = 0; i < M; i++)
    {
        if (done[i])
            continue;
        if (donext <= i)
        {
            dp[i].first = 1;
            dp2[i].first = -1;
            donext = M + 10;
        }
        else if (donext != M + 10)
            continue;
        if (dp[i].first == 0)
            continue;
        if (S[nextsprinkle[i]] - K <= F[i])
        {
            if (done[next[nextsprinkle[i]]])
            {
                donext = next[nextsprinkle[i]];
                ans[nextsprinkle[i]] = -1;
                int x = i;
                while (x != -1)
                {
                    if (x >= N)
                        for (int j = 0; j < changes[x - N].second.size(); j++)
                            ans[changes[x - N].second[j].first] = changes[x - N].second[j].second;
                    else
                        for (int j = 0; j < changes[x].first.size(); j++)
                            ans[changes[x].first[j].first] = changes[x].first[j].second;
                    if (x >= N)
                        x = dp2[x - N].second;
                    else
                        x = dp2[x].first;
                }
            }
            dp[next[nextsprinkle[i]]].first = 1;
            dp2[next[nextsprinkle[i]]].first = i;
            changes[next[nextsprinkle[i]]].first.push_back({nextsprinkle[i], -1});
            if (nextsprinkle[i] < N && S[nextsprinkle[i] + 1] - K <= F[i])
            {
                if (done[after[nextsprinkle[i]]])
                {
                    donext = after[nextsprinkle[i]];
                    ans[nextsprinkle[i]] = 1;
                    ans[nextsprinkle[i] + 1] = -1;
                    int x = i;
                    while (x != -1)
                    {
                        if (x >= N)
                            for (int j = 0; j < changes[x - N].second.size(); j++)
                                ans[changes[x - N].second[j].first] = changes[x - N].second[j].second;
                        else
                            for (int j = 0; j < changes[x].first.size(); j++)
                                ans[changes[x].first[j].first] = changes[x].first[j].second;
                        if (x >= N)
                            x = dp2[x - N].second;
                        else
                            x = dp2[x].first;
                    }
                }
                if (F[after[nextsprinkle[i]]] > S[nextsprinkle[i] + 2])
                {
                    dp[after[nextsprinkle[i]]].second = 1;
                    dp2[after[nextsprinkle[i]]].second = i;
                    changes[after[nextsprinkle[i]]].second.push_back({nextsprinkle[i], 1});
                    changes[after[nextsprinkle[i]]].second.push_back({nextsprinkle[i] + 1, -1});
                }
                changes[after[nextsprinkle[i]]].first.push_back({nextsprinkle[i], 1});
                changes[after[nextsprinkle[i]]].first.push_back({nextsprinkle[i] + 1, -1});
                dp[after[nextsprinkle[i]]].first = 1;
                dp2[after[nextsprinkle[i]]].first = i;
            }
        }
        if (dp[i].second == 1)
        {
            if (done[after[nextsprinkle[i] - 1]])
            {
                donext = after[nextsprinkle[i] - 1];
                ans[nextsprinkle[i] - 1] = 1;
                int x = i + N;
                while (x != -1)
                {
                    if (x >= N)
                        for (int j = 0; j < changes[x - N].second.size(); j++)
                            ans[changes[x - N].second[j].first] = changes[x - N].second[j].second;
                    else
                        for (int j = 0; j < changes[x].first.size(); j++)
                            ans[changes[x].first[j].first] = changes[x].first[j].second;
                    if (x >= N)
                        x = dp2[x - N].second;
                    else
                        x = dp2[x].first;
                }
            }
            dp[after[nextsprinkle[i] - 1]].first = 1;
            dp2[after[nextsprinkle[i] - 1]].first = i + N;
            changes[after[nextsprinkle[i] - 1]].first.push_back({nextsprinkle[i] - 1, 1});
            if (F[after[nextsprinkle[i] - 1]] > S[nextsprinkle[i]])
            {
                dp[after[nextsprinkle[i] - 1]].second = 1;
                dp2[after[nextsprinkle[i] - 1]].second = i + N;
                changes[after[nextsprinkle[i] - 1]].second.push_back({nextsprinkle[i] - 1, 1});
            }
        }
    }
    F.pop_back();
    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 + 1);
    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 'bool solve(std::vector<int>&, std::vector<int>&, int, std::vector<int>&)':
Main.cpp:138:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |                         for (int j = 0; j < changes[x - N].second.size(); j++)
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:141:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |                         for (int j = 0; j < changes[x].first.size(); j++)
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:163:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |                             for (int j = 0; j < changes[x - N].second.size(); j++)
      |                                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:166:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |                             for (int j = 0; j < changes[x].first.size(); j++)
      |                                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:197:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |                         for (int j = 0; j < changes[x - N].second.size(); j++)
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:200:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |                         for (int j = 0; j < changes[x].first.size(); j++)
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:267:10: warning: unused variable 'b' [-Wunused-variable]
  267 |     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