oj.uz

Submission #1039789

# Submission time Handle Problem Language Result Execution time Memory
1039789 2024-07-31T08:59:56 Z 정지훈(#11027) Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 151 ms 8272 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 (ind==0||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 8 ms 2652 KB Correct
3 Correct 1 ms 2652 KB Correct
4 Correct 8 ms 2496 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 2652 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Correct
2 Correct 12 ms 2652 KB Correct
3 Correct 5 ms 2648 KB Correct
4 Correct 35 ms 3416 KB Correct
5 Correct 36 ms 3412 KB Correct
6 Correct 1 ms 2648 KB Correct
7 Correct 1 ms 2652 KB Correct
8 Correct 21 ms 2868 KB Correct
9 Correct 20 ms 2644 KB Correct
10 Correct 29 ms 2648 KB Correct
11 Correct 12 ms 2652 KB Correct
12 Correct 23 ms 2896 KB Correct
13 Correct 45 ms 4948 KB Correct
14 Correct 51 ms 5220 KB Correct
15 Correct 70 ms 5200 KB Correct
16 Correct 29 ms 4432 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 2396 KB Correct
3 Correct 2 ms 2648 KB Correct
4 Correct 1 ms 2652 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 35 ms 3416 KB Correct
3 Correct 131 ms 8056 KB Correct
4 Correct 151 ms 8272 KB Correct
5 Correct 140 ms 8020 KB Correct
6 Incorrect 147 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 8 ms 2652 KB Correct
4 Correct 1 ms 2652 KB Correct
5 Correct 8 ms 2496 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 2652 KB Correct
11 Correct 12 ms 2652 KB Correct
12 Correct 5 ms 2648 KB Correct
13 Correct 35 ms 3416 KB Correct
14 Correct 36 ms 3412 KB Correct
15 Correct 1 ms 2648 KB Correct
16 Correct 1 ms 2652 KB Correct
17 Correct 21 ms 2868 KB Correct
18 Correct 20 ms 2644 KB Correct
19 Correct 29 ms 2648 KB Correct
20 Correct 12 ms 2652 KB Correct
21 Correct 23 ms 2896 KB Correct
22 Correct 45 ms 4948 KB Correct
23 Correct 51 ms 5220 KB Correct
24 Correct 70 ms 5200 KB Correct
25 Correct 29 ms 4432 KB Correct
26 Correct 2 ms 2648 KB Correct
27 Correct 1 ms 2652 KB Correct
28 Incorrect 1 ms 2652 KB User solution is incorrect
29 Halted 0 ms 0 KB -