Submission #391600

#	Time	Username	Problem	Language	Result	Execution time	Memory
391600		usachevd0	Towns (IOI15_towns)	C++14	13 / 100	21 ms	352 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 __) {
  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 (x != v1 && x != v2 && dc[x] == d[i]) {
            h.push_back(x);
          }
        }
        vector<int> comp(n, -1);
        int C = 0;
        int rem = h.size();
        bool bad = false;
        for (int x : h) {
          if (rem <= n / 2) break;
          if (comp[x] == -1) {
            comp[x] = C++;
            int sz = 1;
            for (int y : h) {
              if (comp[y] == -1 && getDistance(x, y) < cx[x] + cx[y]) {
                ++sz;
                comp[y] = -1;
              }
            }
            if (sz > n / 2) {
              bad = true;
              break;
            }
            rem -= sz;
          }
        }
        if (!bad) {
          found = true;
          break;
        }
        /*bool bad = false;
        for (int itr = 0; itr < 2e9; ++itr) {
          if (h.size() <= n / 2) {
            break;
          }
          int x = h[(rng() % h.size() + h.size()) % h.size()];
          int sz = 0;
          vector<int> new_h;
          for (int y : h) {
            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("towns.in", "r", stdin);
#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, 1) << '\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: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 < cnt.size(); ++i) {
      |                   ~~^~~~~~~~~~~~
towns.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for (int i = 0; i < d.size(); ++i) {
      |                   ~~^~~~~~~~~~
towns.cpp:99:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (int i = 0; i < d.size(); ++i) {
      |                   ~~^~~~~~~~~~
towns.cpp:114:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  114 |         int rem = h.size();
      |                   ~~~~~~^~
towns.cpp:43:28: warning: unused parameter '__' [-Wunused-parameter]
   43 | 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