oj.uz

Submission #1105046

# Submission time Handle Problem Language Result Execution time Memory
1105046 2024-10-25T08:45:02 Z SalihSahin Sprinklers (CEOI24_sprinklers) C++14
9 / 100
 83 ms 5180 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]});
            }
        }

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

    int ans = l;
    if(ans == mod){
        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;
            }
        }
    }

    int cover = 0;
    for(int i = 0; i < n; i++){
        if(cover == m) break;
        if(!d[i] && f[cover] >= s[i] - ans){
            cover = us[i];
        }
        if(d[i] && f[cover] >= s[i]){
            cover = right[i];
        }
    }

    if(cover != m){
        for(int i = 0; i < 6e6; i++){
            int x = 5;
            x += 17;
        }
    }

    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 504 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Correct
2 Correct 9 ms 1104 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 10 ms 1240 KB Correct
5 Correct 10 ms 1104 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 368 KB Correct
8 Correct 3 ms 592 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 55 ms 5180 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 35 ms 5076 KB Correct
9 Correct 51 ms 5160 KB Correct
10 Correct 53 ms 5068 KB Correct
11 Correct 27 ms 4668 KB Correct
12 Correct 26 ms 2600 KB Correct
13 Correct 45 ms 4884 KB Correct
14 Correct 49 ms 4932 KB Correct
15 Correct 47 ms 4920 KB Correct
16 Correct 50 ms 4920 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 504 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 1 ms 396 KB Correct
5 Incorrect 1 ms 504 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 16 ms 1616 KB Correct
3 Incorrect 83 ms 5172 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 504 KB Correct
3 Correct 9 ms 1104 KB Correct
4 Correct 1 ms 336 KB Correct
5 Correct 10 ms 1240 KB Correct
6 Correct 10 ms 1104 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 1 ms 368 KB Correct
9 Correct 3 ms 592 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 55 ms 5180 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 35 ms 5076 KB Correct
18 Correct 51 ms 5160 KB Correct
19 Correct 53 ms 5068 KB Correct
20 Correct 27 ms 4668 KB Correct
21 Correct 26 ms 2600 KB Correct
22 Correct 45 ms 4884 KB Correct
23 Correct 49 ms 4932 KB Correct
24 Correct 47 ms 4920 KB Correct
25 Correct 50 ms 4920 KB Correct
26 Correct 1 ms 336 KB Correct
27 Correct 1 ms 396 KB Correct
28 Incorrect 1 ms 504 KB User solution is incorrect
29 Halted 0 ms 0 KB -