oj.uz

답안 #1074978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074978 2024-08-25T17:17:22 Z raphaelp Sprinklers (CEOI24_sprinklers) C++14
9 / 100
 2000 ms 15092 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 = 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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 348 KB Correct

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 46 ms 7032 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 27 ms 2264 KB Correct
5 Correct 26 ms 2260 KB Correct
6 Correct 0 ms 432 KB Correct
7 Correct 0 ms 344 KB Correct
8 Correct 6 ms 876 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 58 ms 9000 KB Correct
3 Correct 18 ms 1300 KB Correct
4 Correct 256 ms 14028 KB Correct
5 Correct 263 ms 14100 KB Correct
6 Correct 1 ms 344 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 157 ms 8716 KB Correct
9 Correct 161 ms 8852 KB Correct
10 Correct 226 ms 12936 KB Correct
11 Correct 153 ms 7356 KB Correct
12 Correct 119 ms 10316 KB Correct
13 Correct 234 ms 10376 KB Correct
14 Correct 229 ms 11352 KB Correct
15 Correct 203 ms 11452 KB Correct
16 Correct 186 ms 7648 KB Correct

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 2 ms 348 KB Correct
6 Incorrect 1 ms 448 KB User solution is incorrect
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 64 ms 8032 KB Correct
3 Correct 253 ms 14856 KB Correct
4 Correct 260 ms 15092 KB Correct
5 Correct 258 ms 14484 KB Correct
6 Correct 272 ms 14856 KB Correct
7 Correct 260 ms 15056 KB Correct
8 Correct 253 ms 15056 KB Correct
9 Correct 263 ms 14884 KB Correct
10 Correct 294 ms 14788 KB Correct
11 Correct 288 ms 15052 KB Correct
12 Correct 0 ms 348 KB Correct
13 Correct 1 ms 348 KB Correct
14 Correct 144 ms 7444 KB Correct
15 Correct 138 ms 7448 KB Correct
16 Correct 129 ms 7420 KB Correct
17 Correct 128 ms 7400 KB Correct
18 Correct 154 ms 7576 KB Correct
19 Correct 160 ms 7788 KB Correct
20 Correct 256 ms 14560 KB Correct
21 Correct 238 ms 14504 KB Correct
22 Correct 251 ms 13528 KB Correct
23 Correct 262 ms 13700 KB Correct
24 Correct 189 ms 7908 KB Correct
25 Correct 176 ms 7924 KB Correct
26 Correct 133 ms 6532 KB Correct
27 Correct 87 ms 4660 KB Correct
28 Correct 243 ms 10648 KB Correct
29 Correct 160 ms 7700 KB Correct
30 Correct 168 ms 8608 KB Correct
31 Execution timed out 2017 ms 12164 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 348 KB Correct
3 Correct 46 ms 7032 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 27 ms 2264 KB Correct
6 Correct 26 ms 2260 KB Correct
7 Correct 0 ms 432 KB Correct
8 Correct 0 ms 344 KB Correct
9 Correct 6 ms 876 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 58 ms 9000 KB Correct
12 Correct 18 ms 1300 KB Correct
13 Correct 256 ms 14028 KB Correct
14 Correct 263 ms 14100 KB Correct
15 Correct 1 ms 344 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 157 ms 8716 KB Correct
18 Correct 161 ms 8852 KB Correct
19 Correct 226 ms 12936 KB Correct
20 Correct 153 ms 7356 KB Correct
21 Correct 119 ms 10316 KB Correct
22 Correct 234 ms 10376 KB Correct
23 Correct 229 ms 11352 KB Correct
24 Correct 203 ms 11452 KB Correct
25 Correct 186 ms 7648 KB Correct
26 Correct 1 ms 344 KB Correct
27 Correct 1 ms 348 KB Correct
28 Correct 2 ms 348 KB Correct
29 Incorrect 1 ms 448 KB User solution is incorrect
30 Halted 0 ms 0 KB -