Submission #235708

#	Time	Username	Problem	Language	Result	Execution time	Memory
235708		ryansee	Towns (IOI15_towns)	C++14	13 / 100	27 ms	1024 KiB

towns

#include "towns.h"
#include "bits/stdc++.h"
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
 
using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 
 
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
 
int hubDistance(int n, int sub) {
  ll q=0;
	vector<vector<ll>> memo;
	memo.resize(n, vector<ll>(n, -1));
	auto ask=[&](ll x,ll y){
      if(x>y)swap(x,y);
      q+=memo[x][y]==-1;
      assert(q<=n*(n+1)/2);
		
		if(x==y)return 0ll;
		if(~memo[x][y]) return memo[x][y];
		return memo[x][y]=ll(getDistance(x,y));
	};
	ll e1=0, e2=0;
	FOR(i,0,n-1) {
		if(ask(0, i) > ask(0, e1))e1=e2=i;
	}
	FOR(i,0,n-1) {
		if(ask(e1, i) > ask(e1, e2))e2=i;
	}
	ll diam=ask(e1,e2);
	// cerr<<e1<<' '<<e2<<' '<<diam<<'\n';
	ll r=LLINF;
	vector<ll> dist_fromb;
	vector<ll> dist(n,0);
	FOR(i,0,n-1){
		ll own=(ask(e1,0)+ask(e1,i)-ask(0,i))/2;
		dist[i]=own;
		if(max(own,diam-own)<r) {
			dist_fromb.clear();
			dist_fromb.eb(own);
			r=max(own,diam-own);
		}else if(max(own,diam-own)==r) {
			dist_fromb.eb(own);
		}
	}
  
	sort(all(dist_fromb));
	dist_fromb.resize(unique(all(dist_fromb))-dist_fromb.begin());
	assert(dist_fromb.size() == 1 || dist_fromb.size() == 2);
	if(dist_fromb.size() == 2){
		ll crit=dist[e2], co=0;
		assert(dist[0]>=crit);
		FOR(i,0,n-1)if(dist[i]>=crit){
			assert(i^e1);
			++ co;
		}
		if(co <= n/2) {
			dist_fromb.pop_back();
		} else {
			dist_fromb.erase(dist_fromb.begin());
		}
	}
	ll cent=dist_fromb[0];
	// cerr<<"cent: "<<cent<<'\n';
	auto same=[&](ll x,ll y){
		return (ask(e1,x)+ask(e1,y)-ask(x,y))/2 != cent && ((dist[x] >= cent) == (dist[y] >= cent));
	};
	// FOR(i,0,n-1)FOR(j,i+1,n-1){
		// cerr<<i<<' '<<j<<": "<<same(i,j)<<'\n';
	// }
	vector<ll>last,bin;//all in bin at one point of time, are of same type
	FOR(i,0,n-1) {
		if(last.empty() || !same(last.back(), i)) {
			last.eb(i);
			if(bin.size()) {
				last.eb(bin.back());
				bin.pop_back();
			}
		}else {
			bin.eb(i);
		}
	}
	ll M=last.back(), sz=1+bin.size(); // a representative of the majority!!!!
	// all those in bin, are part of majority
	for(ll i=siz(last)-3; i>=0; --i) {
		if(same(last[i], M)){
			++ sz;
			-- i;
		}
	}
	// cerr<<"sz: "<<sz<<'\n';
	if(sz > n/2) r *= -1;
	return r;
}

Compilation message (stderr)

towns.cpp: In lambda function:
towns.cpp:43:39: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return memo[x][y]=ll(getDistance(x,y));
                                       ^
towns.cpp:43:39: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:115:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return r;
         ^
towns.cpp:32:28: warning: unused parameter 'sub' [-Wunused-parameter]
 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