oj.uz

Submission #278760

# Submission time Handle Problem Language Result Execution time Memory
278760 2020-08-21T19:55:11 Z Haunted_Cpp Best Place (NOI17_bestplace) C++17
100 / 100
 132 ms 3196 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;
  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.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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 288 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 1152 KB Output is correct
2 Correct 117 ms 1152 KB Output is correct
3 Correct 115 ms 1280 KB Output is correct
4 Correct 115 ms 1152 KB Output is correct
5 Correct 116 ms 1152 KB Output is correct
6 Correct 118 ms 1152 KB Output is correct
7 Correct 115 ms 1152 KB Output is correct
8 Correct 115 ms 1152 KB Output is correct

Subtask #4
13.0 / 13.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 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct

Subtask #5
17.0 / 17.0

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

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 1152 KB Output is correct
2 Correct 120 ms 3072 KB Output is correct
3 Correct 121 ms 3072 KB Output is correct
4 Correct 118 ms 2304 KB Output is correct
5 Correct 124 ms 3196 KB Output is correct
6 Correct 132 ms 3072 KB Output is correct
7 Correct 128 ms 3072 KB Output is correct
8 Correct 123 ms 3072 KB Output is correct