Submission #371284

#	Time	Username	Problem	Language	Result	Execution time	Memory
371284		Mamnoon_Siam	Towns (IOI15_towns)	C++17	13 / 100	24 ms	492 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;
  function<int(int,int)> get = [&mem](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)];
    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));
  }
  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;
  };
  if(center_cnt == 2) {
    int left_cnt = 0, right_cnt = 0;
    for(auto x : dia) {
      if(x.fi <= dia_len - R) left_cnt += sz(x.se);
      else right_cnt += sz(x.se);
    }
    if(left_cnt == right_cnt) return R;
    return -R;
  } else if(center_cnt == 1) {
    int d12C = -1;
    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 cnt = 0;
    for(int i : mid) {
      if(std::get<0>(hands(d1, piv, i)) != d12C)
        ++cnt;
    }
    if(cnt > N/2) return -R;
    return R;
  } else {
    assert(false);
    return 69;
  }
}

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:99:3: note: in expansion of macro 'debug'
   99 |   debug(d1, d2);
      |   ^~~~~
towns.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 42
      |                    ^~
towns.cpp:100:3: note: in expansion of macro 'debug'
  100 |   debug(center_cnt);
      |   ^~~~~
towns.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 42
      |                    ^~
towns.cpp:130:5: note: in expansion of macro 'debug'
  130 |     debug(d12C);
      |     ^~~~~
towns.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 42
      |                    ^~
towns.cpp:133:7: note: in expansion of macro 'debug'
  133 |       debug(i);
      |       ^~~~~
towns.cpp:60:28: warning: unused parameter 'sub' [-Wunused-parameter]
   60 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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