oj.uz

Submission #1047095

# Submission time Handle Problem Language Result Execution time Memory
1047095 2024-08-07T08:53:38 Z VahanAbraham Sprinklers (CEOI24_sprinklers) C++17
100 / 100
 74 ms 7512 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>

using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 200005;
const ll oo = 100000000000000000, MOD = 1000000007;

ll s[N], f[N], dp[N];
int n, m;
char pat[N], ans[N];

int func(int ind, ll l, ll r) {
    while (f[ind] >= l && f[ind] <= r && ind<=m) {
        ++ind;
    }
    --ind;
    return ind;
}

int func1(int ind, ll l, ll r,ll l1,ll r1) {
    while (ind<=m) {
        if ((f[ind] >= l && f[ind] <= r) || (f[ind] >= l1 && f[ind] <= r1)) {
            ++ind;
        }
        else {
            break;
        }
    }
    --ind;
    return ind;
}

bool from[N][5];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> f[i];
    }
    ll l = 0, r = 10000000000, anss = oo;
    while (l <= r) {
        ll mid = (l + r) / 2;
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = 0;
            for (int j = 0; j < 3; ++j) {
                from[i][j] = 0;
            }
        }
        for (int i = 0; i <= n-1; ++i) {
            int ind = dp[i];
            ++ind;
            ind = func(ind, s[i+1] - mid, s[i+1]);
            if (ind > dp[i + 1]) {
                dp[i + 1] = ind;
                for (int j = 0; j < 3; ++j) {
                    from[i + 1][j] = 0;
                }
                from[i + 1][0] = 1;
                ans[i + 1] = 'L';
            }
            ind = dp[i];
            ++ind;
            ind = func(ind, s[i+1], s[i+1] + mid);
            if (ind > dp[i + 1]) {
                dp[i + 1] = ind;
                for (int j = 0; j < 3; ++j) {
                    from[i + 1][j] = 0;
                }
                from[i + 1][1] = 1;
                ans[i + 1] = 'R';
            }
            ind = dp[i] + 1;
            ind = func1(ind, s[i+1], s[i+1] + mid, s[i + 2] - mid, s[i + 2]);
            if (ind > dp[i + 2]) {
                for (int j = 0; j < 3; ++j) {
                    from[i + 2][j] = 0;
                }
                from[i + 2][2] = 1;
                ans[i + 1] = 'R';
                dp[i + 2] = ind;
                ans[i + 2] = 'L';
            }
        }
        if (dp[n] == m) {
            for (int i = n; i >= 1; --i) {
                if (from[i][0] == 1) {
                    pat[i] = 'L';
                }
                else {
                    if (from[i][1] == 1) {
                        pat[i] = 'R';
                    }
                    else {
                        pat[i] = 'L';
                        pat[i - 1] = 'R';
                        --i;
                    }
                }
            }
            anss = min(anss, mid);
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    if (anss == oo) {
        cout << -1 << endl;
        return;
    }
    cout << anss << endl;
    for (int i = 1; i <= n; ++i) {
        cout << pat[i];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 1 ms 4564 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4564 KB Correct
2 Correct 6 ms 5212 KB Correct
3 Correct 0 ms 4444 KB Correct
4 Correct 7 ms 5448 KB Correct
5 Correct 7 ms 5468 KB Correct
6 Correct 1 ms 4444 KB Correct
7 Correct 0 ms 4444 KB Correct
8 Correct 2 ms 4700 KB Correct
9 Correct 1 ms 4444 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 13 ms 5344 KB Correct
3 Correct 5 ms 4700 KB Correct
4 Correct 46 ms 7512 KB Correct
5 Correct 45 ms 7508 KB Correct
6 Correct 1 ms 4440 KB Correct
7 Correct 1 ms 4444 KB Correct
8 Correct 33 ms 7508 KB Correct
9 Correct 33 ms 7468 KB Correct
10 Correct 37 ms 7504 KB Correct
11 Correct 25 ms 6496 KB Correct
12 Correct 23 ms 6236 KB Correct
13 Correct 36 ms 6492 KB Correct
14 Correct 37 ms 6800 KB Correct
15 Correct 42 ms 6800 KB Correct
16 Correct 36 ms 6492 KB Correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 1 ms 4564 KB Correct
3 Correct 1 ms 4440 KB Correct
4 Correct 0 ms 4444 KB Correct
5 Correct 1 ms 4444 KB Correct
6 Correct 0 ms 4444 KB Correct
7 Correct 1 ms 4444 KB Correct
8 Correct 1 ms 4444 KB Correct
9 Correct 1 ms 4444 KB Correct
10 Correct 1 ms 4444 KB Correct
11 Correct 1 ms 4444 KB Correct
12 Correct 0 ms 4444 KB Correct
13 Correct 0 ms 4444 KB Correct
14 Correct 0 ms 4572 KB Correct
15 Correct 1 ms 4444 KB Correct
16 Correct 0 ms 4444 KB Correct
17 Correct 1 ms 4444 KB Correct
18 Correct 1 ms 4444 KB Correct
19 Correct 1 ms 4444 KB Correct
20 Correct 1 ms 4444 KB Correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 15 ms 5724 KB Correct
3 Correct 62 ms 7456 KB Correct
4 Correct 67 ms 7456 KB Correct
5 Correct 74 ms 7504 KB Correct
6 Correct 62 ms 7504 KB Correct
7 Correct 65 ms 7460 KB Correct
8 Correct 65 ms 7440 KB Correct
9 Correct 61 ms 7456 KB Correct
10 Correct 60 ms 7504 KB Correct
11 Correct 60 ms 7504 KB Correct
12 Correct 1 ms 4444 KB Correct
13 Correct 1 ms 4444 KB Correct
14 Correct 40 ms 6492 KB Correct
15 Correct 26 ms 6492 KB Correct
16 Correct 27 ms 6492 KB Correct
17 Correct 30 ms 5980 KB Correct
18 Correct 30 ms 6328 KB Correct
19 Correct 34 ms 6480 KB Correct
20 Correct 52 ms 7004 KB Correct
21 Correct 56 ms 7072 KB Correct
22 Correct 49 ms 6876 KB Correct
23 Correct 54 ms 6744 KB Correct
24 Correct 47 ms 6740 KB Correct
25 Correct 53 ms 6708 KB Correct
26 Correct 28 ms 6236 KB Correct
27 Correct 21 ms 5724 KB Correct
28 Correct 43 ms 6492 KB Correct
29 Correct 40 ms 6492 KB Correct
30 Correct 50 ms 6544 KB Correct
31 Correct 41 ms 6680 KB Correct

Subtask #5
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 1 ms 4564 KB Correct
3 Correct 6 ms 5212 KB Correct
4 Correct 0 ms 4444 KB Correct
5 Correct 7 ms 5448 KB Correct
6 Correct 7 ms 5468 KB Correct
7 Correct 1 ms 4444 KB Correct
8 Correct 0 ms 4444 KB Correct
9 Correct 2 ms 4700 KB Correct
10 Correct 1 ms 4444 KB Correct
11 Correct 13 ms 5344 KB Correct
12 Correct 5 ms 4700 KB Correct
13 Correct 46 ms 7512 KB Correct
14 Correct 45 ms 7508 KB Correct
15 Correct 1 ms 4440 KB Correct
16 Correct 1 ms 4444 KB Correct
17 Correct 33 ms 7508 KB Correct
18 Correct 33 ms 7468 KB Correct
19 Correct 37 ms 7504 KB Correct
20 Correct 25 ms 6496 KB Correct
21 Correct 23 ms 6236 KB Correct
22 Correct 36 ms 6492 KB Correct
23 Correct 37 ms 6800 KB Correct
24 Correct 42 ms 6800 KB Correct
25 Correct 36 ms 6492 KB Correct
26 Correct 1 ms 4440 KB Correct
27 Correct 0 ms 4444 KB Correct
28 Correct 1 ms 4444 KB Correct
29 Correct 0 ms 4444 KB Correct
30 Correct 1 ms 4444 KB Correct
31 Correct 1 ms 4444 KB Correct
32 Correct 1 ms 4444 KB Correct
33 Correct 1 ms 4444 KB Correct
34 Correct 1 ms 4444 KB Correct
35 Correct 0 ms 4444 KB Correct
36 Correct 0 ms 4444 KB Correct
37 Correct 0 ms 4572 KB Correct
38 Correct 1 ms 4444 KB Correct
39 Correct 0 ms 4444 KB Correct
40 Correct 1 ms 4444 KB Correct
41 Correct 1 ms 4444 KB Correct
42 Correct 1 ms 4444 KB Correct
43 Correct 1 ms 4444 KB Correct
44 Correct 15 ms 5724 KB Correct
45 Correct 62 ms 7456 KB Correct
46 Correct 67 ms 7456 KB Correct
47 Correct 74 ms 7504 KB Correct
48 Correct 62 ms 7504 KB Correct
49 Correct 65 ms 7460 KB Correct
50 Correct 65 ms 7440 KB Correct
51 Correct 61 ms 7456 KB Correct
52 Correct 60 ms 7504 KB Correct
53 Correct 60 ms 7504 KB Correct
54 Correct 1 ms 4444 KB Correct
55 Correct 1 ms 4444 KB Correct
56 Correct 40 ms 6492 KB Correct
57 Correct 26 ms 6492 KB Correct
58 Correct 27 ms 6492 KB Correct
59 Correct 30 ms 5980 KB Correct
60 Correct 30 ms 6328 KB Correct
61 Correct 34 ms 6480 KB Correct
62 Correct 52 ms 7004 KB Correct
63 Correct 56 ms 7072 KB Correct
64 Correct 49 ms 6876 KB Correct
65 Correct 54 ms 6744 KB Correct
66 Correct 47 ms 6740 KB Correct
67 Correct 53 ms 6708 KB Correct
68 Correct 28 ms 6236 KB Correct
69 Correct 21 ms 5724 KB Correct
70 Correct 43 ms 6492 KB Correct
71 Correct 40 ms 6492 KB Correct
72 Correct 50 ms 6544 KB Correct
73 Correct 41 ms 6680 KB Correct
74 Correct 11 ms 5464 KB Correct
75 Correct 58 ms 7460 KB Correct
76 Correct 61 ms 7508 KB Correct
77 Correct 1 ms 4440 KB Correct
78 Correct 33 ms 7488 KB Correct
79 Correct 38 ms 7508 KB Correct
80 Correct 31 ms 7484 KB Correct
81 Correct 26 ms 6492 KB Correct
82 Correct 28 ms 6492 KB Correct
83 Correct 26 ms 6488 KB Correct
84 Correct 8 ms 5208 KB Correct
85 Correct 53 ms 7060 KB Correct
86 Correct 47 ms 6996 KB Correct
87 Correct 37 ms 6492 KB Correct
88 Correct 10 ms 5456 KB Correct
89 Correct 10 ms 5464 KB Correct