oj.uz

Submission #1075588

# Submission time Handle Problem Language Result Execution time Memory
1075588 2024-08-26T07:55:11 Z raphaelp Sprinklers (CEOI24_sprinklers) C++14
0 / 100
 2000 ms 11832 KB 
#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();
    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 + M;
            changes[y].first = {{x, 1}};
            if (x < N - 1 && y < M && S[x + 1] < F[y])
            {
                dp[y].second = i + M;
                changes[y].second = {{x, 1}};
            }
        }
    }

    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

Main.cpp: In function 'bool solve(std::vector<int>&, std::vector<int>&, int, std::vector<int>&)':
Main.cpp:68: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]
   68 |                 for (int i = 0; i < changes[x - M].second.size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:74: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]
   74 |                 for (int i = 0; i < changes[x].first.size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:125:10: warning: unused variable 'b' [-Wunused-variable]
  125 |     bool b = solve(S, F, L, ans);
      |          ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 33 ms 5636 KB Correct
3 Execution timed out 2082 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 45 ms 6612 KB Correct
3 Correct 25 ms 944 KB Correct
4 Correct 353 ms 9936 KB Correct
5 Correct 394 ms 9824 KB Correct
6 Execution timed out 2044 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 1 ms 348 KB Correct
6 Correct 1 ms 344 KB Correct
7 Execution timed out 2098 ms 348 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 103 ms 6020 KB Correct
3 Execution timed out 2070 ms 11832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 33 ms 5636 KB Correct
4 Execution timed out 2082 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -