oj.uz

Submission #312562

# Submission time Handle Problem Language Result Execution time Memory
312562 2020-10-13T17:35:40 Z monus1042 Cipele (COCI18_cipele) C++17
90 / 90
 45 ms 3080 KB 
// NK
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define psf push_front
#define pof pop_front
#define mkp make_pair
#define all(x) x.begin(), x.end()
#define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr)

vi a,b;
int n,m;

bool fun(int t){
  int p = 0;
  for (int i=0; i<n; ++i){
    while (p<m && abs(a[i] - b[p]) > t) ++p;
    if (p == m) return 0;
    ++p;
  }
  return 1;
}

void solve(){
  cin>>n>>m;
  for (int i=0; i<n; ++i){
    int x; cin>>x;
    a.pb(x);
  }
  for (int i=0; i<m; ++i){
    int x; cin>>x;
    b.pb(x);
  }

  sort(all(a)), sort(all(b));
  if (a.size() > b.size()) swap(a,b), swap(n,m);

  int hi = -1, lo = 2e9;
  while(hi != lo-1){
    int mid = (lo+hi) / 2;
    if (fun(mid)) lo = mid;
    else hi = mid;
  }
  cout<<lo<<'\n';
}

int main(){
  Bolivia_is_nice;
  int t = 1; //cin>>t;
  while(t--)
    solve();
	
  return 0;
}
/*
  ~/.emacs
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1660 KB Output is correct
2 Correct 45 ms 1660 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1592 KB Output is correct
2 Correct 45 ms 1524 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 524 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1532 KB Output is correct
2 Correct 28 ms 2092 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1532 KB Output is correct
2 Correct 22 ms 2300 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1532 KB Output is correct
2 Correct 39 ms 3080 KB Output is correct