oj.uz

Submission #1039788

# Submission time Handle Problem Language Result Execution time Memory
1039788 2024-07-31T08:59:14 Z 정지훈(#11027) Sprinklers (CEOI24_sprinklers) C++17
3 / 100
 153 ms 8276 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[100000];
int b[100000];
int pos[100000];
typedef pair<int,int> P;
int dp[100000][3];
int k;

int getpr(int bi) {
    int ai=lower_bound(a,a+n,b[bi])-a;
    return ai-1;
}

int ans(int ind,int t) {
if (ind==m) return 1;
    if (dp[ind][t]!=-1) {
        return dp[ind][t];
    }
    int in=lower_bound(a,a+n,b[ind])-a;
    int ret=0;
    if (t==0) {
        if (in>0&&a[in-1]>=b[ind]-k) {
            int ni=upper_bound(b,b+m,a[in-1]+k)-b;
            return dp[ind][t]=ans(ni,0);
        }
        else if (in!=n&&a[in]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in])-b;
            if (getpr(ni)!=in) {
                ret|=ans(ni,0);
            }
            else {
                ret|=ans(ni,1);
            }
            ret|=ans(ind,2);
return dp[ind][t]=ret;
        }
        else {
            return dp[ind][t]=0;
        }
    }
    if (t==1) {
        if (in>1&&a[in-2]>=b[ind]-k) {
            int ni=upper_bound(b,b+m,a[in-2]+k)-b;
            if (getpr(ni)!=in-1) {
                return dp[ind][t]=ans(ni,0);
            }
            else {
                return dp[ind][t]=ans(ni,1);
            }
        }
        else if (in!=n&&a[in]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in])-b;
            if (getpr(ni)!=in) {
                ret|=ans(ni,0);
            }
            else {
                ret|=ans(ni,1);
            }
            ret|=ans(ind,2);
        }
        else {
            return dp[ind][t]=0;
        }
        return dp[ind][t]=ret;
    }
    if (t==2) {
        if (in<n-1&&a[in+1]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in]+k)-b;
            if (getpr(ni)!=in+1) {
                ret|=ans(ni,0);
            }
            else {
                ret|=ans(ni,1);
            }
            return dp[ind][t]=ret;
        }
        else {
            return dp[ind][t]=0;
        }
    }
}

void track(int ind,int t) {
if (ind==m) return;
    int in=lower_bound(a,a+n,b[ind])-a;
    int ret=0;
    if (t==0) {
        if (in>0&&a[in-1]>=b[ind]-k) {
            int ni=upper_bound(b,b+m,a[in-1]+k)-b;
            pos[in-1]=1;
            track(ni,0);
            return;
        }
        else if (in!=n&&a[in]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in])-b;
            if (getpr(ni)!=in) {
                if (ans(ni,0)) {
                    pos[in]=0;
                    track(ni,0);
                    return;
                }
                ret|=ans(ni,0);
            }
            else {
                if (ans(ni,1)) {
                    pos[in]=0;
                    track(ni,1);
                    return;
                }
                ret|=ans(ni,1);
            }
                if (ans(ind,2)) {
                    pos[in]=1;
                    track(ind,2);
                    return;
                }
            ret|=ans(ind,2);
        }
        else {
            return;
        }
    }
    if (t==1) {
        if (in>1&&a[in-2]>=b[ind]-k) {
            int ni=upper_bound(b,b+m,a[in-2]+k)-b;
pos[in-2]=1;
            if (getpr(ni)!=in-1) {
                track(ni,0);
            }
            else {
                track(ni,1);
            }
            return;
        }
        else if (in!=n&&a[in]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in])-b;
            if (getpr(ni)!=in) {
                if (ans(ni,0)) {
                    pos[in]=0;
                    track(ni,0);
                    return;
                }
            }
            else {
                if (ans(ni,1)) {
                    pos[in]=0;
                    track(ni,1);
                    return;
                }
            }
                if (ans(ind,2)) {
                    pos[in]=1;
                    track(ind,2);
                    return;
                }
        }
        else {
            return;
        }
    }
    if (t==2) {
        if (in<n-1&&a[in+1]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in]+k)-b;
            if (getpr(ni)!=in+1) {
                if (ans(ni,0)) {
                    pos[in+1]=0;
                    track(ni,0);
                    return;
                }
            }
            else {
                if (ans(ni,1)) {
                    pos[in+1]=0;
                    track(ni,1);
                    return;
                }
            }
            return;
        }
        else {
            return;
        }
    }
}

int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
    }
int ind=0;
    for(int i=0;i<m;i++) {
        int x;
scanf("%d",&x);
int ix=lower_bound(a,a+n,x)-a;
if (ix!=n&&a[ix]==x) {}
else if (b[ind-1]!=x){
b[ind++]=x;
}
    }
m=ind;
    int lo=-1; //impossible
    int hi=1e9+7; //possible
    if (n==1) {
        int f=-1;
        for(int i=0;i<m;i++) {
            if (b[i]<a[0]) {
                if (f==1) {
                    f=2;
                    break;
                }
                f=0;
            }
            if (b[i]>a[0]) {
                if (f==0) {
                    f=2;
                    break;
                }
                f=1;
            }
        }
        if (f==2) {
            printf("-1");
            return 0;
        }
    }
    while (lo+1<hi) {
        int mid=(lo+hi)/2;
        memset(dp,-1,sizeof(dp));
        k=mid;
        if (ans(0,0)) {
            hi=mid;
        }
        else {
            lo=mid;
        }
    }
    k=hi;
memset(dp,-1,sizeof(dp));
    ans(0,0);
    track(0,0);
    printf("%d\n",hi);
    for(int i=0;i<n;i++) {
        printf("%c",pos[i]?'R':'L');
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int ans(int, int)':
Main.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
   84 | }
      | ^
Main.cpp: In function 'int main()':
Main.cpp:190:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:192:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:197:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 | scanf("%d",&x);
      | ~~~~~^~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Correct
2 Correct 9 ms 2648 KB Correct
3 Correct 1 ms 2652 KB Correct
4 Correct 8 ms 2488 KB Correct
5 Correct 9 ms 2396 KB Correct
6 Correct 1 ms 2652 KB Correct
7 Correct 1 ms 2652 KB Correct
8 Correct 2 ms 2396 KB Correct
9 Correct 1 ms 2652 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Correct
2 Correct 13 ms 2648 KB Correct
3 Correct 5 ms 2648 KB Correct
4 Correct 34 ms 3420 KB Correct
5 Correct 37 ms 3412 KB Correct
6 Correct 1 ms 2652 KB Correct
7 Correct 1 ms 2652 KB Correct
8 Incorrect 27 ms 2860 KB User solution is incorrect
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Correct
2 Correct 0 ms 2396 KB Correct
3 Correct 2 ms 2648 KB Correct
4 Correct 1 ms 2648 KB Correct
5 Incorrect 1 ms 2668 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 2652 KB Correct
2 Correct 42 ms 3420 KB Correct
3 Correct 153 ms 8080 KB Correct
4 Correct 149 ms 8276 KB Correct
5 Correct 145 ms 8020 KB Correct
6 Incorrect 151 ms 8016 KB User solution is incorrect
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Correct
2 Correct 0 ms 2396 KB Correct
3 Correct 9 ms 2648 KB Correct
4 Correct 1 ms 2652 KB Correct
5 Correct 8 ms 2488 KB Correct
6 Correct 9 ms 2396 KB Correct
7 Correct 1 ms 2652 KB Correct
8 Correct 1 ms 2652 KB Correct
9 Correct 2 ms 2396 KB Correct
10 Correct 1 ms 2652 KB Correct
11 Correct 13 ms 2648 KB Correct
12 Correct 5 ms 2648 KB Correct
13 Correct 34 ms 3420 KB Correct
14 Correct 37 ms 3412 KB Correct
15 Correct 1 ms 2652 KB Correct
16 Correct 1 ms 2652 KB Correct
17 Incorrect 27 ms 2860 KB User solution is incorrect
18 Halted 0 ms 0 KB -