제출 #391576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391576		usachevd0	도시들 (IOI15_towns)	C++14	13 / 100	27 ms	356 KiB

towns

#include <bits/stdc++.h>
#ifndef DEBUG
  #include <towns.h>
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto x : v) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; }

int hubDistance(int n, int __) {
  mt19937 rng(228); 
 
  auto get_all_from = [&](int v) -> vector<int> {
    vector<int> d(n, 0);
    for (int u = 0; u < n; ++u) {
      if (u != v) {
        d[u] = getDistance(v, u);
      }
    }
    return d;
  };
  auto d0 = get_all_from(0);
  int v1 = max_element(all(d0)) - d0.begin();
  auto d1 = get_all_from(v1);
  int v2 = max_element(all(d1)) - d1.begin();
  int D = d1[v2];
  auto d2 = get_all_from(v2);

  vector<int> d = {0, D};
  vector<int> dc(n), cx(n);
  dc[v1] = 0;
  dc[v2] = D;
  cx[v1] = cx[v2] = 0;
  for (int x = 0; x < n; ++x) {
    if (x != v1 && x != v2) {
      cx[x] = (d1[x] + d2[x] - D) / 2;
      dc[x] = d1[x] - cx[x];
      d.push_back(dc[x]);
    }
  }
  sort(all(d));
  vector<int> cnt;
  vector<int> nd;
  for (int x : d) {
    if (nd.empty() || nd.back() < x) {
      nd.push_back(x);
      cnt.push_back(1);
    } else {
      ++cnt.back();
    }
  }
  swap(d, nd);
  vector<int> pref_c(cnt.size() + 1, 0);
  for (int i = 0; i < cnt.size(); ++i) {
    pref_c[i + 1] = pref_c[i] + cnt[i];
  }
  vector<int> suf_c(cnt.size() + 1, 0);
  for (int i = (int)cnt.size() - 1; i >= 0; --i) {
    suf_c[i] = suf_c[i + 1] + cnt[i];
  }
  int R = 1e9;
  for (int i = 0; i < d.size(); ++i) {
    chkmin(R, max(d[i], D - d[i]));
  }
  bool found = false;
  for (int i = 0; i < d.size(); ++i) {
    if (max(d[i], D - d[i]) == R && max(pref_c[i], suf_c[i + 1]) <= n / 2) {
      if (cnt[i] <= n / 2) {
        found = true;
        break;
      } else {
        // once
        vector<int> h;
        for (int x = 0; x < n; ++x) {
          if (dc[x] == d[i]) {
            h.push_back(x);
          }
        }
        bool bad = false;
        for (int itr = 0; itr < 2; ++itr) {
          if (h.size() <= n / 2) {
            break;
          }
          int x = h[rng() % h.size()];
          int sz = 0;
          vector<int> new_h;
          for (int y = 0; y < h.size(); ++y) {
            if (x == y || getDistance(x, y) < cx[x] + cx[y]) {
              ++sz;
            } else {
              new_h.push_back(y);
            }
          }
          if (sz > n / 2) {
            bad = true;
            break;
          } else {
            swap(h, new_h);
          }
        }
        if (!bad) {
          found = true;
          break;
        }
      }
    }
  }
  if (found) {
    return R;
  } else {
    return -R;
  }
}

#ifdef DEBUG
signed main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

    
  return 0;
}
#endif

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:48:33: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   48 |   int v1 = max_element(all(d0)) - d0.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:50:33: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   50 |   int v2 = max_element(all(d1)) - d1.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for (int i = 0; i < cnt.size(); ++i) {
      |                   ~~^~~~~~~~~~~~
towns.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int i = 0; i < d.size(); ++i) {
      |                   ~~^~~~~~~~~~
towns.cpp:91:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for (int i = 0; i < d.size(); ++i) {
      |                   ~~^~~~~~~~~~
towns.cpp:106:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |           if (h.size() <= n / 2) {
      |               ~~~~~~~~~^~~~~~~~
towns.cpp:112:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |           for (int y = 0; y < h.size(); ++y) {
      |                           ~~^~~~~~~~~~
towns.cpp:35:28: warning: unused parameter '__' [-Wunused-parameter]
   35 | int hubDistance(int n, int __) {
      |                        ~~~~^~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39