Submission #391685

#	Time	Username	Problem	Language	Result	Execution time	Memory
391685		usachevd0	Towns (IOI15_towns)	C++17	100 / 100	27 ms	848 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; }

#ifdef DEBUG
  int n;
  int dist[110][110];
  int getDistance(int i, int j) {
    return dist[i][j];
  }
#endif

int hubDistance(int n, int subtask) {
  mt19937 rng(2282); 
 
  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];

  vector<int> d = {};
  vector<int> dc(n), cx(n);
  for (int x = 0; x < n; ++x) {
    dc[x] = (d1[x] + d1[0] - d0[x]) / 2;
    cx[x] = d1[x] - dc[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;
  if (subtask >= 3) 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 if (subtask != 4) {
        // once
        vector<int> h;
        for (int x = 0; x < n; ++x) {
          if (x != v1 && x != v2 && dc[x] == d[i]) {
            h.push_back(x);
          }
        }
        auto eq = [&](int x, int y) -> bool {
          return x == y || getDistance(x, y) < cx[x] + cx[y];
        };
        vector<int> a, b;
        for (int x : h) {
          if (a.empty() || !eq(x, a.back())) {
            a.push_back(x);
            if (!b.empty()) {
              a.push_back(b.back());
              b.pop_back();
            }
          } else {
            b.push_back(x);
          }
        }

        int T = a.back();
        int pairs = 0;
        while (!a.empty()) {
          if (eq(T, a.back())) {
            if (a.size() == 1) {
              b.push_back(a.back());
              a.pop_back();
              break;
            }
            a.pop_back();
            a.pop_back();
            ++pairs;
          } else {
            if (b.empty()) {
              return R;
            }
            b.pop_back();
            a.pop_back();
            ++pairs;
          }
        }
        if (pairs + b.size() <= n / 2) {
          return R;
          found = true;
          break;
        }
      }
    }
  }
  if (found) {
    return R;
  } else {
    return -R;
  }
}

#ifdef DEBUG
signed main() {
#ifdef DEBUG
  freopen("01", "r", stdin);
  //freopen("01.out", "w", stdout);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> dist[i][j];
    }
  }
  cout << hubDistance(n, 3) << '\n';
    
  return 0;
}
#endif

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:56:33: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   56 |   int v1 = max_element(all(d0)) - d0.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:58:33: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   58 |   int v2 = max_element(all(d1)) - d1.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for (int i = 0; i < cnt.size(); ++i) {
      |                   ~~^~~~~~~~~~~~
towns.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int i = 0; i < d.size(); ++i) {
      |                   ~~^~~~~~~~~~
towns.cpp:93:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   if (subtask >= 3) for (int i = 0; i < d.size(); ++i) {
      |                                     ~~^~~~~~~~~~
towns.cpp:143:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  143 |         if (pairs + b.size() <= n / 2) {
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~

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