oj.uz

Submission #1039637

# Submission time Handle Problem Language Result Execution time Memory
1039637 2024-07-31T06:24:42 Z 정지훈(#11027) Sprinklers (CEOI24_sprinklers) C++17
0 / 100
 9 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[100000];
int b[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]) {
            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++;
                    }
                    used=in+2;
                }
                else {
                    while (ind<m&&b[ind]<=a[in+1]+k) {
                        ind++;
                    }
                    used=in+2;
                }
            }
            else {
                while (ind<m&&b[ind]<=a[in]) {
                    ind++;
                }
                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;
        }
    }
    printf("%d",hi);
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d",&b[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 3.0

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

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -