oj.uz

Submission #1075734

# Submission time Handle Problem Language Result Execution time Memory
1075734 2024-08-26T08:54:21 Z raphaelp Sprinklers (CEOI24_sprinklers) C++14
3 / 100
 2000 ms 11820 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 + ((i == 0) ? 0 : 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 1 ms 348 KB Correct
2 Correct 1 ms 348 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 36 ms 6608 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 25 ms 2176 KB Correct
5 Correct 25 ms 2252 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 5 ms 668 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 44 ms 7592 KB Correct
3 Correct 26 ms 1100 KB Correct
4 Correct 349 ms 11672 KB Correct
5 Correct 381 ms 11820 KB Correct
6 Correct 1 ms 348 KB Correct
7 Correct 0 ms 344 KB Correct
8 Correct 57 ms 5032 KB Correct
9 Correct 56 ms 5228 KB Correct
10 Correct 192 ms 9200 KB Correct
11 Execution timed out 2073 ms 2128 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 1 ms 348 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 1 ms 348 KB Correct
6 Correct 1 ms 440 KB Correct
7 Execution timed out 2053 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 1 ms 348 KB Correct
2 Correct 104 ms 7196 KB Correct
3 Correct 447 ms 11568 KB Correct
4 Execution timed out 2036 ms 11808 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 1 ms 348 KB Correct
3 Correct 36 ms 6608 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 25 ms 2176 KB Correct
6 Correct 25 ms 2252 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 5 ms 668 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 44 ms 7592 KB Correct
12 Correct 26 ms 1100 KB Correct
13 Correct 349 ms 11672 KB Correct
14 Correct 381 ms 11820 KB Correct
15 Correct 1 ms 348 KB Correct
16 Correct 0 ms 344 KB Correct
17 Correct 57 ms 5032 KB Correct
18 Correct 56 ms 5228 KB Correct
19 Correct 192 ms 9200 KB Correct
20 Execution timed out 2073 ms 2128 KB Time limit exceeded
21 Halted 0 ms 0 KB -