[KOI] 백준 8983 - 사냥꾼

https://www.acmicpc.net/problem/8983

풀이

각 동물과 사대들의 거리를 생각해보자.

사대들과의 거리를 그래프 형태로 그리면 다음과 같은 형태가 나옴을 눈치챌 수 있다.

 

 

그래프의 형태는 유니모달 함수이며 우리는 삼분 탐색으로 닿을 수 있는 가장 짧은 사대를 찾을 수 있음을 알 수 있다.

 

사대의 좌표를 정렬한 후 입력받은 동물 좌표마다 삼분 탐색을 실시하여 피격당할 수 있는 동물의 마릿수를 구하면 된다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int m, n, range;
int ar[100000];
 
void solve()
{
  cin >> m >> n >> range;
  int ans = 0;
 
  for (int i = 0; i < m; i++)
  {
    cin >> ar[i];
  }
  sort(ar, ar + m);
  for (int i = 0; i < n; i++)
  {
    ll x, y;
    cin >> x >> y;
 
    int l = 0, r = m - 1;
    bool nice = false;
 
    while (l <= r)
    {
      int diff = (r - l) / 3;
      int p1 = l + diff;
      int p2 = r - diff;
      ll dist1 = abs(x - ar[p1]) + y;
      ll dist2 = abs(x - ar[p2]) + y;
 
      if (dist1 <= range or dist2 <= range)
      {
        nice = true;
        break;
      }
 
      if (dist1 > dist2)
      {
        l = p1 + 1;
      }
      else
      {
        r = p2 - 1;
      }
    }
 
    ans += nice;
  }
 
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록