Submission #1075743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075743		raphaelp	Sprinklers (CEOI24_sprinklers)	C++14	100 / 100	647 ms	13080 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);
    vector<pair<int, int>> dp(M + 1, {-1, -1});
    vector<pair<vector<pair<int, int>>, vector<pair<int, int>>>> changes(M + 1);
    dp[0].first = -2;
    if (S[0] < F[0])
        dp[0].second = -2;
    for (int i = 0; i < M; i++)
    {
        if (dp[i].first != -1)
        {
            int x = lower_bound(S.begin(), S.end(), F[i]) - S.begin();
            if (x != N && S[x] - K <= F[i])
            {
                int y = lower_bound(F.begin(), F.end(), S[x]) - F.begin();
                dp[y].first = i;
                changes[y].first = {{x, -1}};
                if (x < N - 1 && y < M && S[x + 1] < F[y])
                {
                    dp[y].second = i;
                    changes[y].second = {{x, -1}};
                }
                if (x < N - 1 && S[x + 1] - K <= F[i])
                {
                    y = upper_bound(F.begin(), F.end(), S[x] + K) - F.begin();
                    dp[y].first = i;
                    changes[y].first = {{x, 1}, {x + 1, -1}};
                    if (x < N - 2 && y < M && S[x + 2] < F[y])
                    {
                        dp[y].second = i;
                        changes[y].second = {{x, 1}, {x + 1, -1}};
                    }
                }
            }
        }
        if (dp[i].second != -1)
        {
            int x = lower_bound(S.begin(), S.end(), F[i]) - S.begin() - 1;
            if (x == -1)
                continue;
            if (S[x] + K < F[i])
                continue;
            int y = upper_bound(F.begin(), F.end(), S[x] + K) - F.begin();
            dp[y].first = i + ((i == 0) ? 0 : M);
            changes[y].first = {{x, 1}};
            if (x < N - 1 && y < M && S[x + 1] < F[y])
            {
                dp[y].second = i + ((i == 0) ? 0 : M);
                changes[y].second = {{x, 1}};
            }
        }
    }
    S.pop_back();
    F.pop_back();
    if (dp[M].first != -1 || dp[M].second != -1)
    {
        int x = 0;
        if (dp[M].first != -1)
            x = M;
        else
            x = M + M;
        while (x != 0)
        {
            if (x > M)
            {
                for (int i = 0; i < changes[x - M].second.size(); i++)
                    ans[changes[x - M].second[i].first] = changes[x - M].second[i].second;
                x = dp[x - M].second;
            }
            else
            {
                for (int i = 0; i < changes[x].first.size(); i++)
                    ans[changes[x].first[i].first] = changes[x].first[i].second;
                x = dp[x].first;
            }
        }
        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:71:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 for (int i = 0; i < changes[x - M].second.size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:77:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                 for (int i = 0; i < changes[x].first.size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:128:10: warning: unused variable 'b' [-Wunused-variable]
  128 |     bool b = solve(S, F, L, ans);
      |          ^

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