oj.uz

Submission #1100537

# Submission time Handle Problem Language Result Execution time Memory
1100537 2024-10-14T08:24:47 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
0 / 100
 306 ms 4688 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 + 1);
                types.push_back(true);
            }
            else {
                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 Incorrect 1 ms 336 KB User solution is incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 3.0

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

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB User solution is incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB User solution is incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB User solution is incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB User solution is incorrect
2 Halted 0 ms 0 KB -