Submission #1100539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1100539	2024-10-14T08:26:21 Z	crafticat	Sprinklers (CEOI24_sprinklers)	C++17	6 / 100	859 ms	11208 KB

Main

#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) 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
0.0 / 3.0

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

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Correct
2	Correct	306 ms	5468 KB	Correct
3	Correct	45 ms	1244 KB	Correct
4	Correct	859 ms	11024 KB	Correct
5	Correct	811 ms	11208 KB	Correct
6	Correct	1 ms	336 KB	Correct
7	Correct	1 ms	336 KB	Correct
8	Correct	672 ms	11012 KB	Correct
9	Correct	816 ms	10968 KB	Correct
10	Correct	851 ms	11208 KB	Correct
11	Correct	272 ms	6084 KB	Correct
12	Correct	460 ms	7088 KB	Correct
13	Correct	719 ms	9420 KB	Correct
14	Correct	646 ms	9420 KB	Correct
15	Correct	638 ms	9428 KB	Correct
16	Correct	653 ms	9424 KB	Correct