Submission #371315

#TimeUsernameProblemLanguageResultExecution timeMemory
371315Mamnoon_SiamTowns (IOI15_towns)C++17
61 / 100
27 ms512 KiB
#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(sub == 4) { return max({sz(le), sz(mid), sz(ri)}) > N/2 ? -R : R; } 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:142:3: note: in expansion of macro 'debug'
  142 |   debug(d12C);
      |   ^~~~~
towns.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 42
      |                    ^~
towns.cpp:145:5: note: in expansion of macro 'debug'
  145 |     debug(i);
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...