oj.uz

Submission #1047165

# Submission time Handle Problem Language Result Execution time Memory
1047165 2024-08-07T09:42:35 Z c2zi6 Sprinklers (CEOI24_sprinklers) C++14
100 / 100
 70 ms 4184 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<bool> VB;
typedef vector<VB> VVB;
 
void solve() {
    int n, m;
    cin >> n >> m;
    VI a(n);
    for (int& x : a) cin >> x;
    VI b(m);
    for (int& x : b) cin >> x;
    auto expand = [&](int last, int L, int R) {
        if (last == m) return m;
        if (b[last] < L) return -1;
        while (last != m && b[last] <= R) last++;
        return last;
    };
    string ans(n, '_');
    auto can = [&](int d) {
        VI dp(n+1, -1);
        VI cs(n+1);
        dp[0] = 0;
        replr(i, 1, n) {
            int case1 = expand(dp[i-1], a[i-1]-d, a[i-1]);
            int case2 = expand(dp[i-1], a[i-1], a[i-1]+d);
            int case3 = -1;
            if (i != 1 && a[i-2] - a[i-1] <= d) {
                case3 = expand(dp[i-2], a[i-1]-d, a[i-2]+d);
            }
            if (case1 > dp[i]) {
                dp[i] = case1;
                cs[i] = 1;
            }
            if (case2 > dp[i]) {
                dp[i] = case2;
                cs[i] = 2;
            }
            if (case3 > dp[i]) {
                dp[i] = case3;
                cs[i] = 3;
            }
            if (dp[i] == -1) return false;
        }
        int cur = n;
        while (cur) {
            if (cs[cur] == 1) {
                ans[--cur] = 'L';
            } else if (cs[cur] == 2) {
                ans[--cur] = 'R';
            } else if (cs[cur] == 3) {
                ans[--cur] = 'L';
                ans[--cur] = 'R';
            }
        }
        return dp[n] == m;
    };
    int l = -1, r = 1e9;
    while (l+1 < r) {
        int m = (l + r) / 2;
        if (can(m)) r = m;
        else l = m;
    }
    if (can(r)) {
        cout << r << endl;
        cout << ans << endl;
    } else {
        cout << -1 << endl;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    /*freopen("mincross.in", "r", stdin); */
    /*freopen("test.out", "w", stdout); */
    int t = 1;
    /*cin >> t; */
    while (t--) solve();
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 5 ms 600 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 6 ms 856 KB Correct
5 Correct 6 ms 856 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1 ms 348 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 8 ms 860 KB Correct
3 Correct 3 ms 604 KB Correct
4 Correct 38 ms 4040 KB Correct
5 Correct 41 ms 4128 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 24 ms 4092 KB Correct
9 Correct 27 ms 4152 KB Correct
10 Correct 44 ms 4148 KB Correct
11 Correct 22 ms 2704 KB Correct
12 Correct 18 ms 2500 KB Correct
13 Correct 33 ms 3064 KB Correct
14 Correct 33 ms 3276 KB Correct
15 Correct 38 ms 3472 KB Correct
16 Correct 31 ms 3100 KB Correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 0 ms 348 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 0 ms 344 KB Correct
10 Correct 0 ms 460 KB Correct
11 Correct 0 ms 348 KB Correct
12 Correct 0 ms 348 KB Correct
13 Correct 0 ms 468 KB Correct
14 Correct 0 ms 348 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 0 ms 348 KB Correct
18 Correct 0 ms 348 KB Correct
19 Correct 0 ms 348 KB Correct
20 Correct 0 ms 348 KB Correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 12 ms 860 KB Correct
3 Correct 59 ms 2136 KB Correct
4 Correct 62 ms 4184 KB Correct
5 Correct 70 ms 4084 KB Correct
6 Correct 62 ms 4088 KB Correct
7 Correct 60 ms 4128 KB Correct
8 Correct 65 ms 4124 KB Correct
9 Correct 63 ms 4072 KB Correct
10 Correct 59 ms 4084 KB Correct
11 Correct 64 ms 4040 KB Correct
12 Correct 1 ms 348 KB Correct
13 Correct 0 ms 348 KB Correct
14 Correct 25 ms 2712 KB Correct
15 Correct 26 ms 2716 KB Correct
16 Correct 31 ms 2720 KB Correct
17 Correct 26 ms 2800 KB Correct
18 Correct 37 ms 2860 KB Correct
19 Correct 30 ms 3064 KB Correct
20 Correct 50 ms 3700 KB Correct
21 Correct 50 ms 3668 KB Correct
22 Correct 46 ms 3556 KB Correct
23 Correct 47 ms 3444 KB Correct
24 Correct 43 ms 3276 KB Correct
25 Correct 43 ms 3276 KB Correct
26 Correct 24 ms 2476 KB Correct
27 Correct 23 ms 1728 KB Correct
28 Correct 41 ms 3132 KB Correct
29 Correct 45 ms 2984 KB Correct
30 Correct 41 ms 3032 KB Correct
31 Correct 34 ms 3184 KB Correct

Subtask #5
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Correct 5 ms 600 KB Correct
4 Correct 0 ms 344 KB Correct
5 Correct 6 ms 856 KB Correct
6 Correct 6 ms 856 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 1 ms 348 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 8 ms 860 KB Correct
12 Correct 3 ms 604 KB Correct
13 Correct 38 ms 4040 KB Correct
14 Correct 41 ms 4128 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 24 ms 4092 KB Correct
18 Correct 27 ms 4152 KB Correct
19 Correct 44 ms 4148 KB Correct
20 Correct 22 ms 2704 KB Correct
21 Correct 18 ms 2500 KB Correct
22 Correct 33 ms 3064 KB Correct
23 Correct 33 ms 3276 KB Correct
24 Correct 38 ms 3472 KB Correct
25 Correct 31 ms 3100 KB Correct
26 Correct 0 ms 348 KB Correct
27 Correct 0 ms 348 KB Correct
28 Correct 0 ms 348 KB Correct
29 Correct 0 ms 348 KB Correct
30 Correct 0 ms 348 KB Correct
31 Correct 0 ms 348 KB Correct
32 Correct 0 ms 344 KB Correct
33 Correct 0 ms 460 KB Correct
34 Correct 0 ms 348 KB Correct
35 Correct 0 ms 348 KB Correct
36 Correct 0 ms 468 KB Correct
37 Correct 0 ms 348 KB Correct
38 Correct 0 ms 348 KB Correct
39 Correct 0 ms 348 KB Correct
40 Correct 0 ms 348 KB Correct
41 Correct 0 ms 348 KB Correct
42 Correct 0 ms 348 KB Correct
43 Correct 0 ms 348 KB Correct
44 Correct 12 ms 860 KB Correct
45 Correct 59 ms 2136 KB Correct
46 Correct 62 ms 4184 KB Correct
47 Correct 70 ms 4084 KB Correct
48 Correct 62 ms 4088 KB Correct
49 Correct 60 ms 4128 KB Correct
50 Correct 65 ms 4124 KB Correct
51 Correct 63 ms 4072 KB Correct
52 Correct 59 ms 4084 KB Correct
53 Correct 64 ms 4040 KB Correct
54 Correct 1 ms 348 KB Correct
55 Correct 0 ms 348 KB Correct
56 Correct 25 ms 2712 KB Correct
57 Correct 26 ms 2716 KB Correct
58 Correct 31 ms 2720 KB Correct
59 Correct 26 ms 2800 KB Correct
60 Correct 37 ms 2860 KB Correct
61 Correct 30 ms 3064 KB Correct
62 Correct 50 ms 3700 KB Correct
63 Correct 50 ms 3668 KB Correct
64 Correct 46 ms 3556 KB Correct
65 Correct 47 ms 3444 KB Correct
66 Correct 43 ms 3276 KB Correct
67 Correct 43 ms 3276 KB Correct
68 Correct 24 ms 2476 KB Correct
69 Correct 23 ms 1728 KB Correct
70 Correct 41 ms 3132 KB Correct
71 Correct 45 ms 2984 KB Correct
72 Correct 41 ms 3032 KB Correct
73 Correct 34 ms 3184 KB Correct
74 Correct 8 ms 1884 KB Correct
75 Correct 51 ms 4036 KB Correct
76 Correct 58 ms 4116 KB Correct
77 Correct 0 ms 348 KB Correct
78 Correct 21 ms 4080 KB Correct
79 Correct 37 ms 4072 KB Correct
80 Correct 21 ms 4076 KB Correct
81 Correct 24 ms 2700 KB Correct
82 Correct 24 ms 2716 KB Correct
83 Correct 23 ms 2716 KB Correct
84 Correct 7 ms 1116 KB Correct
85 Correct 41 ms 3264 KB Correct
86 Correct 47 ms 3416 KB Correct
87 Correct 32 ms 3076 KB Correct
88 Correct 7 ms 1628 KB Correct
89 Correct 8 ms 1628 KB Correct