Submission #278759

#	Time	Username	Problem	Language	Result	Execution time	Memory
278759		Haunted_Cpp	Best Place (NOI17_bestplace)	C++17	64 / 100	1083 ms	3072 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;
  bool all_zero = true;
  i64 s_x = 0;
  i64 s_y = 0;
  vector<pair<int, int>> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i].first >> arr[i].second;
    all_zero &= (arr[i].second == 0);
    s_x += arr[i].first;
    s_y += 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;
    };
  if (all_zero) {
    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 << ' ' << 0 << '\n';
  } else {
    tuple<i64, i64, i64> best_way = make_tuple(1e18, -1, -1);
    i64 start_x = s_x / n;
    i64 start_y = s_y / n;
    for (i64 i = start_x - 100; i < start_x + 100; i++) {
      for (i64 j = start_y - 100; j < start_y + 100; j++) {
        best_way = min(best_way, make_tuple(solve(i, j), i, j));
      }
    }
    cout << get<1>(best_way) << ' ' << get<2>(best_way) << '\n';
  }
  return 0;
}

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