oj.uz

Submission #1074986

# Submission time Handle Problem Language Result Execution time Memory
1074986 2024-08-25T17:19:02 Z raphaelp Sprinklers (CEOI24_sprinklers) C++14
9 / 100
 2000 ms 13164 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);
    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 = 1000000010;
    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: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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 43 ms 6952 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 25 ms 1208 KB Correct
5 Correct 46 ms 1448 KB Correct
6 Correct 1 ms 344 KB Correct
7 Correct 0 ms 344 KB Correct
8 Correct 6 ms 604 KB Correct
9 Correct 1 ms 344 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 56 ms 8192 KB Correct
3 Correct 18 ms 1160 KB Correct
4 Correct 260 ms 12120 KB Correct
5 Correct 242 ms 12188 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 154 ms 6748 KB Correct
9 Correct 183 ms 6756 KB Correct
10 Correct 228 ms 10924 KB Correct
11 Correct 179 ms 6444 KB Correct
12 Correct 101 ms 9216 KB Correct
13 Correct 228 ms 9340 KB Correct
14 Correct 195 ms 9992 KB Correct
15 Correct 223 ms 10076 KB Correct
16 Correct 172 ms 6760 KB Correct

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 348 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 1 ms 348 KB Correct
6 Incorrect 1 ms 348 KB User solution is incorrect
7 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 65 ms 7300 KB Correct
3 Correct 263 ms 12896 KB Correct
4 Correct 268 ms 13164 KB Correct
5 Correct 268 ms 12728 KB Correct
6 Correct 260 ms 12924 KB Correct
7 Correct 295 ms 13088 KB Correct
8 Correct 261 ms 12904 KB Correct
9 Correct 264 ms 13048 KB Correct
10 Correct 253 ms 12956 KB Correct
11 Correct 264 ms 13124 KB Correct
12 Correct 1 ms 348 KB Correct
13 Correct 0 ms 348 KB Correct
14 Correct 115 ms 6496 KB Correct
15 Correct 138 ms 6452 KB Correct
16 Correct 119 ms 6504 KB Correct
17 Correct 116 ms 6792 KB Correct
18 Correct 123 ms 6844 KB Correct
19 Correct 133 ms 6900 KB Correct
20 Correct 261 ms 13024 KB Correct
21 Correct 247 ms 12856 KB Correct
22 Correct 275 ms 12356 KB Correct
23 Correct 249 ms 12376 KB Correct
24 Correct 201 ms 6920 KB Correct
25 Correct 164 ms 6696 KB Correct
26 Correct 154 ms 5612 KB Correct
27 Correct 84 ms 4012 KB Correct
28 Correct 219 ms 9100 KB Correct
29 Correct 160 ms 6628 KB Correct
30 Correct 200 ms 7516 KB Correct
31 Execution timed out 2021 ms 10860 KB Time limit exceeded
32 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 43 ms 6952 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 25 ms 1208 KB Correct
6 Correct 46 ms 1448 KB Correct
7 Correct 1 ms 344 KB Correct
8 Correct 0 ms 344 KB Correct
9 Correct 6 ms 604 KB Correct
10 Correct 1 ms 344 KB Correct
11 Correct 56 ms 8192 KB Correct
12 Correct 18 ms 1160 KB Correct
13 Correct 260 ms 12120 KB Correct
14 Correct 242 ms 12188 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 154 ms 6748 KB Correct
18 Correct 183 ms 6756 KB Correct
19 Correct 228 ms 10924 KB Correct
20 Correct 179 ms 6444 KB Correct
21 Correct 101 ms 9216 KB Correct
22 Correct 228 ms 9340 KB Correct
23 Correct 195 ms 9992 KB Correct
24 Correct 223 ms 10076 KB Correct
25 Correct 172 ms 6760 KB Correct
26 Correct 1 ms 348 KB Correct
27 Correct 0 ms 348 KB Correct
28 Correct 1 ms 348 KB Correct
29 Incorrect 1 ms 348 KB User solution is incorrect
30 Halted 0 ms 0 KB -