Submission #118371

#	Time	Username	Problem	Language	Result	Execution time	Memory
118371		OptxPrime	Cipele (COCI18_cipele)	C++11	90 / 90	107 ms	3028 KiB

cipele

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include<queue>
#include<string.h>

using namespace std;
#define pb push_back
#define mp make_pair
#define fb find_best
#define ae add_element
#define ce check_element
#define cs compile_set



int main()
{
        int n,m;
        int l[100010],r[100010],tmp[100010];
        cin>>n>>m;
       //  if( n>m ) swap( n,m );
        for( int i=0;i<n;i++ ) cin>>l[i];
        for(int i=0;i<m;i++) cin>>r[i];
        if( n>m ){
            for( int i=0;i<m;i++ ) tmp[i] = r[i];
            for( int i=0;i<n;i++ ) r[i]=l[i];
            for( int i=0;i<m;i++ ) l[i]=tmp[i];
            swap(n,m);
        }
        sort( l,l+n );
        sort( r,r+m );
       int lo=0,hi= 1000000000,mid,ans=1000000000;
       while(lo<=hi){
        mid=lo+(hi-lo)/2;
      // cout << mid << " kumee " <<endl;
        int curr=n-1;
        bool is=true;
        for( int i=m-1;i>=0;i-- ){
                if(curr<0) break;
            if( i < curr ){ ///nemozemo ih sve uparit
                is=false;
                break;
            }
          //  cout << i << " " << r[i] << " " << curr << " " << l[curr] << " eto " <<endl;
            if( abs( r[i] - l[curr] ) <= mid ){
                curr--;/// uparili smo curr pa sad uparujemo manji
            }
        }
        if( is && curr<0 ){ /// moze,probaj jos manju razliku
            hi=mid-1;
            ans=min(ans,mid);
        }
        else lo=mid+1;/// inace, probaj vecu razliku
       }

       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