oj.uz

Submission #1047449

# Submission time Handle Problem Language Result Execution time Memory
1047449 2024-08-07T13:13:44 Z gagik_2007 Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 159 ms 3676 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=100007;
ll n,m,k;
int f[N],s[N];
int dp[N];
int par[N];
bool pardir[N];

int getFlowerAmount(int l, int r){
    auto it1=lower_bound(f+1,f+m+1,l);
    auto it2=upper_bound(f+1,f+m+1,r);
    int cnt=(it2-it1);
    //cout<<"GetFlowerAmount: "<<l<<" "<<r<<" - "<<cnt<<endl;
    return cnt;
}

bool check(int vl){
    //cout<<vl<<endl;
    for(int i=0;i<=n;i++){
        dp[i]=0;
        par[i]=0;
    }
    for(int i=0;i<n;i++){
        if(dp[i+1]<dp[i]){
            dp[i+1]=dp[i];
            par[i+1]=i;
            pardir[i+1]=true;
        }
        int ind=dp[i]+1;
        if(ind==m+1){
            continue;
        }
        if(f[ind]>=s[i+1]&&f[ind]<=s[i+1]+vl){
            //cout<<1<<endl;
            int pos=dp[i]+getFlowerAmount(f[ind],s[i+1]+vl);
            if(pos>dp[i+1]){
                par[i+1]=i;
                pardir[i+1]=true;
            }
            dp[i+1]=max(dp[i+1],pos);
            //cout<<i+1<<" -> "<<dp[i+1]<<endl;
        }
        if(f[ind]>=s[i+1]-vl&&f[ind]<=s[i+1]){
            //cout<<2<<endl;
            int pos=dp[i]+getFlowerAmount(f[ind],s[i+1]);
            if(pos>dp[i+1]){
                par[i+1]=i;
                pardir[i+1]=false;
            }
            dp[i+1]=max(dp[i+1],pos);
            //cout<<i+1<<" -> "<<dp[i+1]<<endl;
        }
        if(i<n-1&&s[i+2]-vl<=s[i+1]&&s[i+2]<=s[i+1]+vl&&f[ind]>=s[i+2]-vl&&f[ind]<=s[i+1]+vl){
            //cout<<3<<endl;
            int pos=dp[i]+getFlowerAmount(f[ind],s[i+1]+vl);
            if(pos>dp[i+2]){
                par[i+2]=i;
            }
            dp[i+2]=max(dp[i+2],pos);
            //cout<<i+2<<" -> "<<dp[i+2]<<endl;
        }
        //cout<<i<<": "<<dp[i]<<endl;
    }
    //cout<<n<<": "<<dp[n]<<endl;
    //cout<<endl;
    if(dp[n]==m){
        return true;
    }
    return false;
}

string getAnswer(){
    string ans="";
    for(int i=0;i<n;i++){
        ans+='L';
    }
    int cur=n;
    while(cur>0){
        if(dp[cur]==0){
            break;
        }
        if(cur-par[cur]==2){
            ans[cur-1]='R';
        }
        else if(pardir[cur]){
            ans[cur-1]='R';
        }
        cur=par[cur];
    }
    return ans;
}

int binsearch(){
    int l=0,r=MOD;
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return l;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt","r",stdin);
    // freopen("wrongout.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    for(int i=1;i<=m;i++){
        cin>>f[i];
    }
    int res=binsearch();
    if(res==MOD){
        cout<<-1<<endl;
        return 0;
    }
    check(res);
    string ans=getAnswer();
    cout<<res<<endl<<ans<<endl;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 6 ms 1116 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 6 ms 1372 KB Correct
5 Correct 7 ms 1372 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1 ms 604 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 348 KB Correct
2 Correct 8 ms 1372 KB Correct
3 Correct 8 ms 604 KB Correct
4 Correct 96 ms 3620 KB Correct
5 Correct 101 ms 3664 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 18 ms 3580 KB Correct
9 Correct 18 ms 3676 KB Correct
10 Correct 18 ms 3676 KB Correct
11 Correct 14 ms 2652 KB Correct
12 Correct 48 ms 2304 KB Correct
13 Correct 61 ms 3056 KB Correct
14 Correct 72 ms 3408 KB Correct
15 Correct 81 ms 3412 KB Correct
16 Correct 53 ms 2900 KB Correct

Subtask #3
0.0 / 17.0

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

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 39 ms 1368 KB Correct
3 Incorrect 159 ms 3156 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 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 6 ms 1116 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 6 ms 1372 KB Correct
6 Correct 7 ms 1372 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 1 ms 604 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 8 ms 1372 KB Correct
12 Correct 8 ms 604 KB Correct
13 Correct 96 ms 3620 KB Correct
14 Correct 101 ms 3664 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 18 ms 3580 KB Correct
18 Correct 18 ms 3676 KB Correct
19 Correct 18 ms 3676 KB Correct
20 Correct 14 ms 2652 KB Correct
21 Correct 48 ms 2304 KB Correct
22 Correct 61 ms 3056 KB Correct
23 Correct 72 ms 3408 KB Correct
24 Correct 81 ms 3412 KB Correct
25 Correct 53 ms 2900 KB Correct
26 Correct 0 ms 348 KB Correct
27 Correct 0 ms 348 KB Correct
28 Correct 1 ms 348 KB Correct
29 Incorrect 0 ms 348 KB User solution is incorrect
30 Halted 0 ms 0 KB -