제출 #278760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
278760		Haunted_Cpp	Best Place (NOI17_bestplace)	C++17	100 / 100	132 ms	3196 KiB

bestplace

/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

typedef long long i64;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int n;
  cin >> n;
  vector<pair<int, int>> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i].first >> arr[i].second;
  }
  auto solve = [&](i64 x, i64 y) -> i64 {
    long long s = 0;
    for (int i = 0; i < n; i++) {
      s += abs(x - arr[i].first) + abs(y - arr[i].second);
    }
    return s;
  };
  int lo = 0, hi = 1e9 + 7;
  while(lo < hi) {
    const int m1 = lo + (hi - lo) / 3;
    const int m2 = hi - (hi - lo) / 3;
    if(solve(m2, 0) > solve(m1, 0)) hi = m2 - 1;
    else lo = m1 + 1;
  }
  cout << lo << ' ';
  lo = 0, hi = 1e9 + 7;
  while(lo < hi) {
    const int m1 = lo + (hi - lo) / 3;
    const int m2 = hi - (hi - lo) / 3;
    if(solve(0, m2) > solve(0, m1)) hi = m2 - 1;
    else lo = m1 + 1;
  }
  cout << lo << '\n';
  return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 20 / 20
• Subtask 3: 28 / 28
• Subtask 4: 13 / 13
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19