oj.uz

Submission #1039638

# Submission time Handle Problem Language Result Execution time Memory
1039638 2024-07-31T06:27:25 Z 정지훈(#11027) Sprinklers (CEOI24_sprinklers) C++17
23 / 100
 86 ms 1600 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[100000];
int b[100000];
int pos[100000];

bool func(int k) {
    int ind=0;
    int used=0;
    while (ind<m) {
        int in=lower_bound(a,a+n,b[ind]-k)-a;
        in=max(in,used);
        if (in==n||a[in]>b[ind]+k) {
            return false;
        }
        if (a[in]<=b[ind]) {
            pos[in]=1;
            while (ind<m&&b[ind]<=a[in]+k) {
                ind++;
            }
            used=in+1;
        }
        else {
            if (in!=n-1&&a[in+1]<=b[ind]+k) {
                bool flag=false;
                if (in<n-2&&a[in+2]<=b[ind]+k) {
                    flag=true;
                }
                else {
                    int ind2=lower_bound(b,b+m,a[ind]+1)-b;
                    if (ind2<m&&b[ind2]<a[in+1]) {
                        flag=true;
                    }
                    else {
                        flag=false;
                    }
                }
                if (flag) {
                    while (ind<m&&b[ind]<=a[in]+k) {
                        ind++;
                    }
                    pos[in]=1;
                    pos[in+1]=0;
                    used=in+2;
                }
                else {
                    while (ind<m&&b[ind]<=a[in+1]+k) {
                        ind++;
                    }
                    pos[in]=0;
                    pos[in+1]=1;
                    used=in+2;
                }
            }
            else {
                while (ind<m&&b[ind]<=a[in]) {
                    ind++;
                }
                pos[in]=0;
                used=in+1;
            }
        }
    }
    return true;
}

int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++) {
        scanf("%d",&b[i]);
    }
    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[i]) {
                if (f==1) {
                    f=2;
                    break;
                }
                f=0;
            }
            if (b[i]>a[i]) {
                if (f==0) {
                    f=2;
                    break;
                }
                f=1;
            }
        }
        if (f==2) {
            printf("-1");
            return 0;
        }
    }
    while (lo+1<hi) {
        int mid=(lo+hi)/2;
        if (func(mid)) {
            hi=mid;
        }
        else {
            lo=mid;
        }
    }
    func(hi);
    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 main()':
Main.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d",&b[i]);
      |         ~~~~~^~~~~~~~~~~~

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
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Incorrect 6 ms 604 KB User solution is worse than jury's solution
3 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 9 ms 600 KB Correct
3 Correct 5 ms 348 KB Correct
4 Correct 53 ms 1560 KB Correct
5 Correct 57 ms 1596 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 27 ms 1228 KB Correct
9 Correct 18 ms 1116 KB Correct
10 Correct 19 ms 1368 KB Correct
11 Correct 11 ms 1116 KB Correct
12 Correct 27 ms 1016 KB Correct
13 Correct 31 ms 1484 KB Correct
14 Correct 34 ms 1368 KB Correct
15 Correct 41 ms 1380 KB Correct
16 Correct 28 ms 1368 KB Correct

Subtask #3
17.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 344 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 1 ms 348 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 0 ms 348 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 0 ms 348 KB Correct
12 Correct 0 ms 348 KB Correct
13 Correct 0 ms 348 KB Correct
14 Correct 0 ms 348 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 0 ms 348 KB Correct
18 Correct 0 ms 348 KB Correct
19 Correct 0 ms 348 KB Correct
20 Correct 0 ms 348 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 19 ms 860 KB Correct
3 Incorrect 86 ms 1600 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 Incorrect 6 ms 604 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -