oj.uz

Submission #1075743

# Submission time Handle Problem Language Result Execution time Memory
1075743 2024-08-26T08:58:25 Z raphaelp Sprinklers (CEOI24_sprinklers) C++14
100 / 100
 647 ms 13080 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();
    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

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 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 32 ms 5760 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 24 ms 1468 KB Correct
5 Correct 26 ms 1472 KB Correct
6 Correct 1 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 5 ms 604 KB Correct
9 Correct 0 ms 344 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 43 ms 6600 KB Correct
3 Correct 25 ms 908 KB Correct
4 Correct 389 ms 9948 KB Correct
5 Correct 375 ms 9944 KB Correct
6 Correct 0 ms 344 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 53 ms 2984 KB Correct
9 Correct 58 ms 3264 KB Correct
10 Correct 194 ms 7136 KB Correct
11 Correct 36 ms 1372 KB Correct
12 Correct 200 ms 7576 KB Correct
13 Correct 263 ms 6320 KB Correct
14 Correct 292 ms 7448 KB Correct
15 Correct 271 ms 7492 KB Correct
16 Correct 172 ms 4436 KB Correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 1 ms 348 KB Correct
6 Correct 1 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1 ms 348 KB Correct
9 Correct 1 ms 348 KB Correct
10 Correct 1 ms 348 KB Correct
11 Correct 0 ms 348 KB Correct
12 Correct 1 ms 344 KB Correct
13 Correct 1 ms 348 KB Correct
14 Correct 0 ms 348 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 1 ms 348 KB Correct
18 Correct 1 ms 348 KB Correct
19 Correct 1 ms 348 KB Correct
20 Correct 1 ms 344 KB Correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 109 ms 6160 KB Correct
3 Correct 496 ms 9644 KB Correct
4 Correct 528 ms 10084 KB Correct
5 Correct 487 ms 9348 KB Correct
6 Correct 499 ms 9716 KB Correct
7 Correct 480 ms 9800 KB Correct
8 Correct 507 ms 9680 KB Correct
9 Correct 514 ms 9716 KB Correct
10 Correct 491 ms 9672 KB Correct
11 Correct 505 ms 9820 KB Correct
12 Correct 0 ms 348 KB Correct
13 Correct 0 ms 348 KB Correct
14 Correct 50 ms 1584 KB Correct
15 Correct 38 ms 2388 KB Correct
16 Correct 34 ms 2388 KB Correct
17 Correct 24 ms 2396 KB Correct
18 Correct 27 ms 2652 KB Correct
19 Correct 32 ms 2908 KB Correct
20 Correct 481 ms 11420 KB Correct
21 Correct 462 ms 11440 KB Correct
22 Correct 421 ms 10284 KB Correct
23 Correct 447 ms 10544 KB Correct
24 Correct 215 ms 5652 KB Correct
25 Correct 196 ms 5692 KB Correct
26 Correct 79 ms 2712 KB Correct
27 Correct 164 ms 4080 KB Correct
28 Correct 336 ms 7292 KB Correct
29 Correct 153 ms 4396 KB Correct
30 Correct 234 ms 5896 KB Correct
31 Correct 575 ms 13040 KB Correct

Subtask #5
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 32 ms 5760 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 24 ms 1468 KB Correct
6 Correct 26 ms 1472 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 5 ms 604 KB Correct
10 Correct 0 ms 344 KB Correct
11 Correct 43 ms 6600 KB Correct
12 Correct 25 ms 908 KB Correct
13 Correct 389 ms 9948 KB Correct
14 Correct 375 ms 9944 KB Correct
15 Correct 0 ms 344 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 53 ms 2984 KB Correct
18 Correct 58 ms 3264 KB Correct
19 Correct 194 ms 7136 KB Correct
20 Correct 36 ms 1372 KB Correct
21 Correct 200 ms 7576 KB Correct
22 Correct 263 ms 6320 KB Correct
23 Correct 292 ms 7448 KB Correct
24 Correct 271 ms 7492 KB Correct
25 Correct 172 ms 4436 KB Correct
26 Correct 1 ms 348 KB Correct
27 Correct 0 ms 348 KB Correct
28 Correct 1 ms 348 KB Correct
29 Correct 1 ms 348 KB Correct
30 Correct 0 ms 348 KB Correct
31 Correct 1 ms 348 KB Correct
32 Correct 1 ms 348 KB Correct
33 Correct 1 ms 348 KB Correct
34 Correct 0 ms 348 KB Correct
35 Correct 1 ms 344 KB Correct
36 Correct 1 ms 348 KB Correct
37 Correct 0 ms 348 KB Correct
38 Correct 0 ms 348 KB Correct
39 Correct 0 ms 348 KB Correct
40 Correct 1 ms 348 KB Correct
41 Correct 1 ms 348 KB Correct
42 Correct 1 ms 348 KB Correct
43 Correct 1 ms 344 KB Correct
44 Correct 109 ms 6160 KB Correct
45 Correct 496 ms 9644 KB Correct
46 Correct 528 ms 10084 KB Correct
47 Correct 487 ms 9348 KB Correct
48 Correct 499 ms 9716 KB Correct
49 Correct 480 ms 9800 KB Correct
50 Correct 507 ms 9680 KB Correct
51 Correct 514 ms 9716 KB Correct
52 Correct 491 ms 9672 KB Correct
53 Correct 505 ms 9820 KB Correct
54 Correct 0 ms 348 KB Correct
55 Correct 0 ms 348 KB Correct
56 Correct 50 ms 1584 KB Correct
57 Correct 38 ms 2388 KB Correct
58 Correct 34 ms 2388 KB Correct
59 Correct 24 ms 2396 KB Correct
60 Correct 27 ms 2652 KB Correct
61 Correct 32 ms 2908 KB Correct
62 Correct 481 ms 11420 KB Correct
63 Correct 462 ms 11440 KB Correct
64 Correct 421 ms 10284 KB Correct
65 Correct 447 ms 10544 KB Correct
66 Correct 215 ms 5652 KB Correct
67 Correct 196 ms 5692 KB Correct
68 Correct 79 ms 2712 KB Correct
69 Correct 164 ms 4080 KB Correct
70 Correct 336 ms 7292 KB Correct
71 Correct 153 ms 4396 KB Correct
72 Correct 234 ms 5896 KB Correct
73 Correct 575 ms 13040 KB Correct
74 Correct 55 ms 7592 KB Correct
75 Correct 491 ms 13080 KB Correct
76 Correct 592 ms 13076 KB Correct
77 Correct 1 ms 344 KB Correct
78 Correct 59 ms 4916 KB Correct
79 Correct 59 ms 4888 KB Correct
80 Correct 99 ms 7444 KB Correct
81 Correct 29 ms 2396 KB Correct
82 Correct 39 ms 2396 KB Correct
83 Correct 37 ms 2384 KB Correct
84 Correct 75 ms 4816 KB Correct
85 Correct 394 ms 9128 KB Correct
86 Correct 405 ms 9320 KB Correct
87 Correct 647 ms 13080 KB Correct
88 Correct 42 ms 7636 KB Correct
89 Correct 47 ms 7632 KB Correct