Submission #1100536

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1100536	2024-10-14T08:24:32 Z	crafticat	Sprinklers (CEOI24_sprinklers)	C++17	0 / 100	834 ms	11392 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 - 1) 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	314 ms	4664 KB	User solution is incorrect
3	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Correct
2	Correct	305 ms	5456 KB	Correct
3	Correct	45 ms	1104 KB	Correct
4	Correct	763 ms	11256 KB	Correct
5	Correct	834 ms	11392 KB	Correct
6	Correct	1 ms	336 KB	Correct
7	Incorrect	1 ms	512 KB	User solution is incorrect
8	Halted	0 ms	0 KB	-