oj.uz

Submission #1053096

# Submission time Handle Problem Language Result Execution time Memory
1053096 2024-08-11T08:45:32 Z elazarkoren Sprinklers (CEOI24_sprinklers) C++17
0 / 100
 19 ms 4308 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e5 + 5;

ll s[MAX_N], f[MAX_N];
int ri[MAX_N];
int n, m;

bool Solve(int k) {
    int i = 0, j = 0;
    vi leftest(n);
    while (i < n && j < m) {
        if (f[j] >= s[i]) {
            leftest[i] = f[j] - s[i] <= k ? j : -1;
            while (j < m && f[j] - s[i] <= k) j++;
            ri[i] = 1;
            i++;
            continue;
        }
        if (s[i] - f[j] > k) return 0;
        ri[i] = 0;
        if (i && leftest[i - 1] != -1 && s[i] - f[leftest[i - 1]] <= k) {
            leftest[i] = leftest[i - 1];
            while (j < m && f[j] - s[i - 1] <= k) j++;
            ri[i - 1] = 1;
        } else {
            leftest[i] = j;
        }
        while (j < m && f[j] <= s[i] && s[i] - f[j] <= k) j++;
        i++;
    }
    return j == m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < m; i++) cin >> f[i];
//    int begin = 0, end = 1e9 + 1;
//    while (begin < end) {
//        int mid = (begin + end) >> 1;
//        if (Solve(mid)) end = mid;
//        else begin = mid + 1;
//    }
    int end;
    for (end = 0; end <= 8; end++) {
        if (Solve(end)) break;
    }
    if (!Solve(end)) {
        cout << -1 << '\n';
        return 0;
    }
    cout << end << '\n';
    for (int i = 0; i < n; i++) {
        cout << (ri[i] ? 'R' : 'L');
    }
}

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

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

Subtask #2
0.0 / 6.0

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

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Incorrect 0 ms 348 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 0 ms 348 KB Correct
2 Correct 7 ms 1372 KB Correct
3 Correct 15 ms 2868 KB Correct
4 Correct 14 ms 2772 KB Correct
5 Correct 14 ms 2824 KB Correct
6 Correct 15 ms 2772 KB Correct
7 Correct 17 ms 2768 KB Correct
8 Correct 19 ms 2768 KB Correct
9 Correct 15 ms 2772 KB Correct
10 Correct 15 ms 2768 KB Correct
11 Correct 16 ms 2768 KB Correct
12 Correct 0 ms 344 KB Correct
13 Correct 0 ms 348 KB Correct
14 Correct 10 ms 2092 KB Correct
15 Correct 8 ms 2004 KB Correct
16 Correct 8 ms 2004 KB Correct
17 Correct 10 ms 2768 KB Correct
18 Correct 11 ms 2840 KB Correct
19 Correct 15 ms 2768 KB Correct
20 Correct 14 ms 2844 KB Correct
21 Correct 14 ms 4308 KB Correct
22 Incorrect 11 ms 3760 KB User solution is worse than jury's solution
23 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 Incorrect 5 ms 1116 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -