oj.uz

Submission #1100535

# Submission time Handle Problem Language Result Execution time Memory
1100535 2024-10-14T08:22:48 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 851 ms 13232 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 {
                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) l++;
    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 340 KB Correct
2 Correct 1 ms 340 KB Correct

Subtask #1
0.0 / 3.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Correct
2 Correct 294 ms 6496 KB Correct
3 Correct 41 ms 1356 KB Correct
4 Correct 799 ms 13100 KB Correct
5 Correct 851 ms 13232 KB Correct
6 Correct 1 ms 340 KB Correct
7 Correct 1 ms 340 KB Correct
8 Correct 704 ms 12952 KB Correct
9 Correct 761 ms 12884 KB Correct
10 Correct 851 ms 13004 KB Correct
11 Correct 259 ms 7112 KB Correct
12 Correct 455 ms 8276 KB Correct
13 Correct 793 ms 10516 KB Correct
14 Correct 699 ms 10724 KB Correct
15 Correct 617 ms 10956 KB Correct
16 Correct 645 ms 10504 KB Correct

Subtask #3
0.0 / 17.0

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

Subtask #4
0.0 / 27.0

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

Subtask #5
0.0 / 47.0

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