oj.uz

Submission #1036547

# Submission time Handle Problem Language Result Execution time Memory
1036547 2024-07-27T13:46:04 Z model_code Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 2000 ms 1288 KB 
// Authors: Robert Jaworski
#include <bits/stdc++.h>

#pragma GCC diagnostic ignored "-Wsign-compare"
using namespace std;

bool check(int K, const std::vector<int>& s, const std::vector<int>& f, const vector<int>& c, bool verbose=false) {
    int i = 0;
    vector<int> cover(f.size(), 0);

    for (; i < s.size(); i++) {
        int l, r;
        if (c[i] == 0) {
            l = s[i] - K;
            r = s[i];
        }
        else {
            l = s[i];
            r = s[i] + K;
        }
        for (int j = 0; j < f.size(); j++) {
            if (l <= f[j] && f[j] <= r) {
                cover[j]++;
            }
        }
    }

    bool covered = true;
    for (auto&& x : cover) {
        covered = x > 0;
        if (!covered) break;
    }
    return covered;
}

bool bruteforce(int N, int M, int K, const vector<int>& s, const vector<int>& f, std::vector<int>& conf) {
    conf.resize(N, 0);
    for (int i = 0; i != N;) {
        if (check(K, s, f, conf)) return true;

        for (i = 0; i < N; i++) {
            conf[i] ^= 1;
            if (conf[i]) break;
        }
    }

    return false;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> s(N, 0), f(M, 0), conf;
    for (auto&& x : s) {
        cin >> x;
    }
    for (auto&& x : f) {
        cin >> x;
    }

    if (N == 1) {
        if (s.back() <= f[0]) {
            cout << (f.back() - s.back()) << endl << "R" << endl;
        }
        else if (s[0] >= f.back()) {
            cout << (s[0] - f[0]) << endl << "L" << endl;
        }
        else {
            cout << -1 << endl;
        }
        return 0;
    }

    int maxK = 1;
    int K, l, r;
    if (bruteforce(N, M, 0, s, f, conf)) {
        K = 0;
        goto END;
    }

    while (!bruteforce(N, M, maxK, s, f, conf)) maxK <<= 1;

    l = maxK / 2;
    r = maxK;
    while (l+1 < r) {
        int m = (l+r) / 2;
        if (bruteforce(N, M, m, s, f, conf)) {
            r = m;
        }
        else {
            l = m;
        }
    }

    K = r;
    if (!bruteforce(N, M, K, s, f, conf)) {
        cout << "Very bad" << endl;
    }

END:
    cout << K << endl;
    for (auto&& x : conf) {
        cout << (x ? 'R' : 'L');
    }
    cout << endl;

    return 0;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 19 ms 604 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 22 ms 832 KB Correct
5 Correct 23 ms 604 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 5 ms 508 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Execution timed out 2068 ms 1216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 95 ms 408 KB Correct
4 Correct 8 ms 436 KB Correct
5 Correct 318 ms 348 KB Correct
6 Correct 359 ms 344 KB Correct
7 Correct 3 ms 344 KB Correct
8 Correct 404 ms 416 KB Correct
9 Correct 374 ms 412 KB Correct
10 Correct 409 ms 420 KB Correct
11 Correct 49 ms 432 KB Correct
12 Correct 338 ms 348 KB Correct
13 Correct 307 ms 344 KB Correct
14 Correct 24 ms 344 KB Correct
15 Correct 31 ms 348 KB Correct
16 Correct 67 ms 412 KB Correct
17 Correct 105 ms 432 KB Correct
18 Correct 14 ms 344 KB Correct
19 Correct 1 ms 348 KB Correct
20 Correct 1 ms 348 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Execution timed out 2065 ms 1288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 19 ms 604 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 22 ms 832 KB Correct
6 Correct 23 ms 604 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 5 ms 508 KB Correct
10 Correct 0 ms 348 KB Correct
11 Execution timed out 2068 ms 1216 KB Time limit exceeded
12 Halted 0 ms 0 KB -