oj.uz

Submission #1105044

# Submission time Handle Problem Language Result Execution time Memory
1105044 2024-10-25T08:38:50 Z SalihSahin Sprinklers (CEOI24_sprinklers) C++14
9 / 100
 95 ms 5184 KB 
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int mod = 1e9 + 7;
const int inf = 1e15;
const int N = 1e5+5;

int32_t main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int n, m;
    cin>>n>>m;
    vector<int> s(n), f(m);
    for(int i = 0; i < n; i++){
        cin>>s[i];
    }
    for(int i = 0; i < m; i++){
        cin>>f[i];
    }

    vector<int> right(n), us(n);
    int l = 0, r = mod;
    while(l < r){
        int mid = (l + r)/2;

        int ind = 0;
        for(int i = 0; i < n; i++){
            while(ind < m && s[i] + mid >= f[ind]) ind++;
            right[i] = ind; // sağı sulayarak alamayacağımız ilk çiçek
        }
        ind = 0;
        for(int i = 0; i < n; i++){
            while(ind < m && s[i] >= f[ind]) ind++;
            us[i] = ind; // benden büyük ilk çiçek
        }

        vector<int> dp(n+1); // dp[i] => ilk i tane sprinkle ile maximum alınabilecek flower prefixi
        for(int i = 0; i < n; i++){
            dp[i+1] = max(dp[i+1], dp[i]);
            if(dp[i] == m) continue;
            int j = dp[i];

            if(s[i] - mid <= f[j]){ // sola
                dp[i+1] = max(dp[i+1], us[i]);
            }
            if(f[j] >= s[i]){
                dp[i+1] = max(dp[i+1], right[i]);
            }
            if(i < n-1 && f[j] <= s[i+1] && s[i+1] - mid <= f[j]){
                dp[i+2] = max({dp[i+2], right[i], us[i+1]});
            }
        }

        if(dp[n] == m) r = mid;
        else l = mid + 1;
    }

    int ans = l;
    if(ans == mod){
        for(int i = 0; i < mod; i++){
            ans++;
        }
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans<<endl;

    int ind = 0;
    for(int i = 0; i < n; i++){
        while(ind < m && s[i] + ans >= f[ind]) ind++;
        right[i] = ind; // sağı sulayarak alabileceğim son çiçek + 1
    }
    ind = 0;
    for(int i = 0; i < n; i++){
        while(ind < m && s[i] >= f[ind]) ind++;
        us[i] = ind; // benden büyük ilk çiçek
    }

    vector<int> dp(n+1); // dp[i] => ilk i tane sprinkle ile maximum alınabilecek flower prefixi
    vector<int> d(n+1);

    for(int i = 0; i < n; i++){
        if(dp[i+1] < dp[i]){
            dp[i+1] = dp[i];
            d[i] = 0;
        }
        if(dp[i] == m) continue;

        int j = dp[i];

        if(s[i] - ans <= f[j]){ // sola
            if(dp[i+1] < us[i]){
                dp[i+1] = us[i];
                d[i] = 0;
            }
        }
        if(f[j] >= s[i]){
            if(dp[i+1] < right[i]){
                dp[i+1] = right[i];
                d[i] = 1;
            }
        }
        if(i < n-1 && f[j] <= s[i+1] && s[i+1] - ans <= f[j]){
            if(dp[i+2] < right[i]){
                dp[i+2] = right[i];
                d[i] = 1;
                d[i+1] = 0;
            }
        }
    }

    for(int i = 0; i < n; i++){
        if(d[i]) cout<<"R";
        else cout<<"L";
    }
    cout<<endl;
    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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 8 ms 1104 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 9 ms 1104 KB Correct
5 Correct 12 ms 1276 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 380 KB Correct
8 Correct 2 ms 764 KB Correct
9 Correct 1 ms 336 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 10 ms 1104 KB Correct
3 Correct 5 ms 848 KB Correct
4 Correct 53 ms 5140 KB Correct
5 Correct 51 ms 5176 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 30 ms 5180 KB Correct
9 Correct 34 ms 5184 KB Correct
10 Correct 42 ms 5172 KB Correct
11 Correct 26 ms 4416 KB Correct
12 Correct 24 ms 2600 KB Correct
13 Correct 42 ms 4916 KB Correct
14 Correct 45 ms 4816 KB Correct
15 Correct 46 ms 4928 KB Correct
16 Correct 40 ms 4928 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 1 ms 336 KB Correct
5 Incorrect 1 ms 336 KB User solution is incorrect
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 18 ms 1616 KB Correct
3 Incorrect 95 ms 5144 KB User solution is incorrect
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Correct 8 ms 1104 KB Correct
4 Correct 1 ms 336 KB Correct
5 Correct 9 ms 1104 KB Correct
6 Correct 12 ms 1276 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 1 ms 380 KB Correct
9 Correct 2 ms 764 KB Correct
10 Correct 1 ms 336 KB Correct
11 Correct 10 ms 1104 KB Correct
12 Correct 5 ms 848 KB Correct
13 Correct 53 ms 5140 KB Correct
14 Correct 51 ms 5176 KB Correct
15 Correct 1 ms 336 KB Correct
16 Correct 1 ms 336 KB Correct
17 Correct 30 ms 5180 KB Correct
18 Correct 34 ms 5184 KB Correct
19 Correct 42 ms 5172 KB Correct
20 Correct 26 ms 4416 KB Correct
21 Correct 24 ms 2600 KB Correct
22 Correct 42 ms 4916 KB Correct
23 Correct 45 ms 4816 KB Correct
24 Correct 46 ms 4928 KB Correct
25 Correct 40 ms 4928 KB Correct
26 Correct 1 ms 336 KB Correct
27 Correct 1 ms 336 KB Correct
28 Incorrect 1 ms 336 KB User solution is incorrect
29 Halted 0 ms 0 KB -