oj.uz

Submission #1039743

# Submission time Handle Problem Language Result Execution time Memory
1039743 2024-07-31T08:18:47 Z 정지훈(#11027) Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 156 ms 8152 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 {
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 2392 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Correct
2 Correct 8 ms 2492 KB Correct
3 Correct 1 ms 2648 KB Correct
4 Correct 8 ms 2488 KB Correct
5 Correct 8 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 2648 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Correct
2 Correct 17 ms 2492 KB Correct
3 Correct 5 ms 2652 KB Correct
4 Correct 35 ms 3420 KB Correct
5 Correct 37 ms 3348 KB Correct
6 Correct 1 ms 2652 KB Correct
7 Correct 1 ms 2652 KB Correct
8 Correct 21 ms 2812 KB Correct
9 Correct 21 ms 2864 KB Correct
10 Correct 22 ms 2652 KB Correct
11 Correct 11 ms 2652 KB Correct
12 Correct 20 ms 2744 KB Correct
13 Correct 41 ms 4948 KB Correct
14 Correct 48 ms 5460 KB Correct
15 Correct 72 ms 5208 KB Correct
16 Correct 29 ms 4388 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Correct
2 Correct 0 ms 2392 KB Correct
3 Correct 1 ms 2652 KB Correct
4 Correct 1 ms 2664 KB Correct
5 Incorrect 1 ms 2652 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 39 ms 3512 KB Correct
3 Correct 156 ms 8016 KB Correct
4 Correct 154 ms 8116 KB Correct
5 Correct 149 ms 8016 KB Correct
6 Incorrect 151 ms 8152 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 2392 KB Correct
3 Correct 8 ms 2492 KB Correct
4 Correct 1 ms 2648 KB Correct
5 Correct 8 ms 2488 KB Correct
6 Correct 8 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 2648 KB Correct
11 Correct 17 ms 2492 KB Correct
12 Correct 5 ms 2652 KB Correct
13 Correct 35 ms 3420 KB Correct
14 Correct 37 ms 3348 KB Correct
15 Correct 1 ms 2652 KB Correct
16 Correct 1 ms 2652 KB Correct
17 Correct 21 ms 2812 KB Correct
18 Correct 21 ms 2864 KB Correct
19 Correct 22 ms 2652 KB Correct
20 Correct 11 ms 2652 KB Correct
21 Correct 20 ms 2744 KB Correct
22 Correct 41 ms 4948 KB Correct
23 Correct 48 ms 5460 KB Correct
24 Correct 72 ms 5208 KB Correct
25 Correct 29 ms 4388 KB Correct
26 Correct 1 ms 2652 KB Correct
27 Correct 1 ms 2664 KB Correct
28 Incorrect 1 ms 2652 KB User solution is incorrect
29 Halted 0 ms 0 KB -