Submission #218987

#	Time	Username	Problem	Language	Result	Execution time	Memory
218987		brcode	Cipele (COCI18_cipele)	C++14	90 / 90	141 ms	3060 KiB

cipele

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9