oj.uz

Submission #118371

# Submission time Handle Problem Language Result Execution time Memory
118371 2019-06-18T20:05:20 Z OptxPrime Cipele (COCI18_cipele) C++11
90 / 90
 107 ms 3028 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 2680 KB Output is correct
2 Correct 102 ms 3028 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2912 KB Output is correct
2 Correct 107 ms 2980 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2468 KB Output is correct
2 Correct 61 ms 2016 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 2892 KB Output is correct
2 Correct 104 ms 2492 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2296 KB Output is correct
2 Correct 88 ms 2908 KB Output is correct