oj.uz

Submission #1105043

# Submission time Handle Problem Language Result Execution time Memory
1105043 2024-10-25T08:37:52 Z SalihSahin Sprinklers (CEOI24_sprinklers) C++14
9 / 100
 96 ms 7224 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){
        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 11 ms 2296 KB Correct
5 Correct 12 ms 2128 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 3 ms 760 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 13 ms 1104 KB Correct
3 Correct 6 ms 1024 KB Correct
4 Correct 55 ms 7012 KB Correct
5 Correct 74 ms 6980 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 36 ms 7100 KB Correct
9 Correct 40 ms 6968 KB Correct
10 Correct 47 ms 7224 KB Correct
11 Correct 28 ms 5432 KB Correct
12 Correct 27 ms 3872 KB Correct
13 Correct 47 ms 5944 KB Correct
14 Correct 50 ms 6164 KB Correct
15 Correct 48 ms 6200 KB Correct
16 Correct 44 ms 5804 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 17 ms 1616 KB Correct
3 Incorrect 96 ms 6968 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 11 ms 2296 KB Correct
6 Correct 12 ms 2128 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 1 ms 336 KB Correct
9 Correct 3 ms 760 KB Correct
10 Correct 1 ms 336 KB Correct
11 Correct 13 ms 1104 KB Correct
12 Correct 6 ms 1024 KB Correct
13 Correct 55 ms 7012 KB Correct
14 Correct 74 ms 6980 KB Correct
15 Correct 1 ms 336 KB Correct
16 Correct 1 ms 336 KB Correct
17 Correct 36 ms 7100 KB Correct
18 Correct 40 ms 6968 KB Correct
19 Correct 47 ms 7224 KB Correct
20 Correct 28 ms 5432 KB Correct
21 Correct 27 ms 3872 KB Correct
22 Correct 47 ms 5944 KB Correct
23 Correct 50 ms 6164 KB Correct
24 Correct 48 ms 6200 KB Correct
25 Correct 44 ms 5804 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 -