Submission #371306

#	Time	Username	Problem	Language	Result	Execution time	Memory
371306		Mamnoon_Siam	Towns (IOI15_towns)	C++17	51 / 100	27 ms	512 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int hubDistance(int N, int sub) {
  map<ii, int> mem;
  int qcnt = 0;
  function<int(int,int)> get = [&mem,&qcnt,&N](int i, int j) {
    if(i == j) return 0;
    if(i > j) swap(i, j);
    if(mem.count(ii(i,j))) return mem[ii(i,j)];
    assert(++qcnt <= 5*N);
    return mem[ii(i,j)] = getDistance(i,j);
  };
  function<tuple<int,int,int>(int,int,int)> hands = [&mem,&get](int A, int B, int C) {
    int AB = get(A, B), BC = get(B, C), CA = get(C, A);
    int a = (AB - BC + CA) / 2;
    int b = (BC - CA + AB) / 2;
    int c = (CA - AB + BC) / 2;
    return make_tuple(a, b, c);
  };
  ii mx1 = {-1, -1};
  for(int i = 1; i < N; ++i) {
    mx1 = max(mx1, ii(get(0, i), i));
  }
  int d1 = mx1.se;
  ii mx2 = {-1, -1};
  for(int i = 0; i < N; ++i) if(i != d1) {
    mx2 = max(mx2, ii(get(d1, i), i));
  }
  int d2 = mx2.se;
  map<int, vi> dia;
  for(int i = 0; i < N; ++i) {
    dia[std::get<0>(hands(d1, d2, i))].emplace_back(i);
  }
  int dia_len = get(d1, d2);
  int R = INT_MAX;
  for(auto x : dia) {
    R = min(R, max(x.fi, dia_len - x.fi));
  }
  if(sub <= 2) return R;
  int center_cnt = 0;
  for(auto x : dia) {
    if(max(x.fi, dia_len - x.fi) == R)
      center_cnt++;
  }
  debug(d1, d2);
  debug(center_cnt);
  function<vi(vi,vi)> add = [](vi a, vi b) {
    vi c;
    sort(all(a)), sort(all(b));
    set_union(all(a), all(b), back_inserter(c));
    return c;
  };
  int d12C = -1;
  map<int, int> cnt;
  if(center_cnt == 2) {
    for(auto x : dia) {
      if(x.fi <= dia_len - R) cnt[dia_len - R] += sz(x.se);
      else cnt[R] += sz(x.se);
    }
    ii left = *cnt.begin();
    ii right = *cnt.rbegin();
    if(left.second >= right.second) {
      d12C = left.first;
    } else {
      d12C = right.first;
    }
  } else {
    for(auto x : dia) {
      if(max(x.fi, dia_len - x.fi) == R) {
        d12C = x.fi;
        break;
      }
    }
  }
  vi le, ri, mid;
  for(auto x : dia) {
    if(x.fi < d12C) le = add(le, x.se);
    else if(x.fi > d12C) ri = add(ri, x.se);
    else mid = add(mid, x.se);
  }
  if(sz(le) > N/2 or sz(ri) > N/2) return -R;
  debug(d12C);
  vi candidate;
  for(int i : mid) {
    debug(i);
    if(candidate.empty()) candidate.push_back(i);
    else if(std::get<0>(hands(d1, candidate.back(), i)) != d12C)
      candidate.push_back(i);
    else candidate.pop_back();
  }
  function<void(vi&,vi&)> pop = [](vi& a, vi& b) {
    if(sz(a) > sz(b)) a.resize(sz(a) - sz(b));
    else a = vi(b.begin(), b.begin() + sz(b)-sz(a));
  };
  pop(candidate, le);
  pop(candidate, ri);
  if(candidate.empty()) return R;
  int piv = candidate.back();
  if(count(all(le), piv) or count(all(ri), piv)) return R;
  int size = 0;
  for(int i : mid) {
    if(std::get<0>(hands(d1, piv, i)) != d12C)
      ++size;
  }
  if(size > N/2) return -R;
  return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 42
      |                    ^~
towns.cpp:102:3: note: in expansion of macro 'debug'
  102 |   debug(d1, d2);
      |   ^~~~~
towns.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 42
      |                    ^~
towns.cpp:103:3: note: in expansion of macro 'debug'
  103 |   debug(center_cnt);
      |   ^~~~~
towns.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 42
      |                    ^~
towns.cpp:139:3: note: in expansion of macro 'debug'
  139 |   debug(d12C);
      |   ^~~~~
towns.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 42
      |                    ^~
towns.cpp:142:5: note: in expansion of macro 'debug'
  142 |     debug(i);
      |     ^~~~~

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