oj.uz

Submission #1100540

# Submission time Handle Problem Language Result Execution time Memory
1100540 2024-10-14T08:27:02 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 965 ms 12992 KB 
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;


vi water, flowers;
V<bool> types;
constexpr int inf = 1e9 + 7;

bool ok(int r) {
    int minP = -1;
    int nextR = -1;

    multiset<pi> data;
    for (auto x : water)
        data.insert({x, -1});
    for (auto x : flowers)
        data.insert({x, 0});

    for (auto [a,b] : data) {
        if (b == -1) {
            if (minP == -1) {
                nextR = max(nextR, a + r);
                types.push_back(true);
            }
            else {
                nextR = max(nextR, a);
                if (minP < a - r) return false;
                else minP = -1;
                types.push_back(false);
            }
        } else {
            if (minP == -1 && a > nextR)
                minP = a;
        }
    }
    return minP == -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, m; cin >> n >> m;
    water.resize(n);
    flowers.resize(m);

    for (int i = 0; i < n; ++i) {
        cin >> water[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> flowers[i];
    }

    int l = 0, r = inf; // Last true
    while (r > l) {
        int mid = l + (r - l) / 2;
        if (ok(mid)) {
            r = mid;
        } else
            l = mid + 1;
    }

    types.clear();
    ok(l);
    if (l == inf) {
        cout << -1;
        return 0;
    }
    if (l == 0) exit(5);
    cout << l << "\n";
    for (auto x : types) {
        cout << (x ? "R" : "L");
    }
    return 0;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 297 ms 4688 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 344 ms 6340 KB Correct
5 Correct 353 ms 6476 KB Correct
6 Correct 1 ms 340 KB Correct
7 Correct 1 ms 340 KB Correct
8 Correct 53 ms 1628 KB Correct
9 Correct 1 ms 340 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 313 ms 5456 KB Correct
3 Correct 57 ms 1380 KB Correct
4 Correct 789 ms 11212 KB Correct
5 Correct 821 ms 11208 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 623 ms 10980 KB Correct
9 Correct 750 ms 10952 KB Correct
10 Correct 810 ms 11096 KB Correct
11 Correct 271 ms 6176 KB Correct
12 Correct 468 ms 6988 KB Correct
13 Correct 692 ms 9460 KB Correct
14 Correct 682 ms 9672 KB Correct
15 Correct 701 ms 9420 KB Correct
16 Correct 706 ms 9420 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Correct 2 ms 336 KB Correct
4 Correct 1 ms 340 KB Correct
5 Incorrect 2 ms 340 KB User solution is worse than jury's solution
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 429 ms 6112 KB Correct
3 Incorrect 965 ms 12992 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Correct 297 ms 4688 KB Correct
4 Correct 1 ms 336 KB Correct
5 Correct 344 ms 6340 KB Correct
6 Correct 353 ms 6476 KB Correct
7 Correct 1 ms 340 KB Correct
8 Correct 1 ms 340 KB Correct
9 Correct 53 ms 1628 KB Correct
10 Correct 1 ms 340 KB Correct
11 Correct 313 ms 5456 KB Correct
12 Correct 57 ms 1380 KB Correct
13 Correct 789 ms 11212 KB Correct
14 Correct 821 ms 11208 KB Correct
15 Correct 1 ms 336 KB Correct
16 Correct 1 ms 336 KB Correct
17 Correct 623 ms 10980 KB Correct
18 Correct 750 ms 10952 KB Correct
19 Correct 810 ms 11096 KB Correct
20 Correct 271 ms 6176 KB Correct
21 Correct 468 ms 6988 KB Correct
22 Correct 692 ms 9460 KB Correct
23 Correct 682 ms 9672 KB Correct
24 Correct 701 ms 9420 KB Correct
25 Correct 706 ms 9420 KB Correct
26 Correct 2 ms 336 KB Correct
27 Correct 1 ms 340 KB Correct
28 Incorrect 2 ms 340 KB User solution is worse than jury's solution
29 Halted 0 ms 0 KB -