oj.uz

Submission #218987

# Submission time Handle Problem Language Result Execution time Memory
218987 2020-04-03T10:47:05 Z brcode Cipele (COCI18_cipele) C++14
90 / 90
 141 ms 3060 KB 
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;
int arr[MAXN];
int arr2[MAXN];
int n,m;
bool check(int x){
    if(n<m){
        int ptr = 1;
        for(int i=1;i<=n;i++){
            while(ptr<=m && abs(arr[i]-arr2[ptr])>x){
                ptr++;
            }
            ptr++;
        }
        if(ptr<=m+1){
            return true;
        }
        
    }else{
        int ptr =  1;
        for(int i=1;i<=m;i++){
            while(ptr<=n && abs(arr[ptr]-arr2[i])>x){
                ptr++;
            }
            ptr++;
        }
    
        if(ptr<=n+1){
            return true;
        }
    }
    return false;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=1;i<=m;i++){
        cin>>arr2[i];
    }
    sort(arr+1,arr+n+1);
    sort(arr2+1,arr2+m+1);
    int l = 0;
    int r= 1e9;
    int ans = r;
    while(l<=r){
        int mid = (l+r)/2;
        if(check(mid)){
            ans = mid;
            r= mid-1;
        }else{
            l= mid+1;
        }
    }
    cout<<ans<<endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 2680 KB Output is correct
2 Correct 141 ms 3060 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 2936 KB Output is correct
2 Correct 139 ms 2944 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 11 ms 512 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 12 ms 512 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 512 KB Output is correct
2 Correct 11 ms 492 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 11 ms 512 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 12 ms 512 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 2424 KB Output is correct
2 Correct 81 ms 1788 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2552 KB Output is correct
2 Correct 83 ms 2040 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 2296 KB Output is correct
2 Correct 119 ms 2680 KB Output is correct