oj.uz

Submission #278759

# Submission time Handle Problem Language Result Execution time Memory
278759 2020-08-21T19:52:25 Z Haunted_Cpp Best Place (NOI17_bestplace) C++17
64 / 100
 1000 ms 3072 KB 
/**
 *  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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 2176 KB Output is correct
2 Correct 69 ms 2304 KB Output is correct
3 Correct 69 ms 2304 KB Output is correct
4 Correct 69 ms 2304 KB Output is correct
5 Correct 78 ms 2296 KB Output is correct
6 Correct 69 ms 2304 KB Output is correct
7 Correct 70 ms 2176 KB Output is correct
8 Correct 71 ms 2304 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 21 ms 384 KB Output is correct
4 Correct 21 ms 384 KB Output is correct
5 Correct 21 ms 384 KB Output is correct
6 Correct 21 ms 384 KB Output is correct
7 Correct 21 ms 384 KB Output is correct
8 Correct 22 ms 384 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 3072 KB Time limit exceeded
2 Halted 0 ms 0 KB -