Submission #453464

#	Time	Username	Problem	Language	Result	Execution time	Memory
453464		PedroBigMan	Towns (IOI15_towns)	C++14	25 / 100	22 ms	352 KiB

towns

#include "towns.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 


int hubDistance(int N, int sub) 
{
	ll D;
	vector<ll> d0; d0.pb(0); REP(i,1,N) {d0.pb(getDistance(0,i));}
	ll A = (ll) (max_element(whole(d0)) - d0.begin());
	vector<ll> d1,d2;
	REP(i,0,N) {if(i==A) {d1.pb(0);} else {d1.pb(getDistance(A,i));}}
	ll B = (ll) (max_element(whole(d1)) - d1.begin());
	D = *max_element(whole(d1));
	REP(i,0,N) {if(i==B) {d2.pb(0);} else {d2.pb(getDistance(B,i));}}
	set<ll> s; 
	REP(i,0,N) {s.insert((d1[i]-d2[i]+D)/2LL);}
	unordered_map<ll,ll> m; set<ll>::iterator it =  s.begin(); ll ind=0LL; 
	ll R=D; vector<ll> poss_ind;
	while(it!=s.end()) 
	{
		R=min(R,max(*it,D-*it));
		m[*it]=ind; ind++; it++;
	}
	it=s.begin(); ind=0;
	while(it!=s.end())
	{
		if(max(*it,D-*it)==R) {poss_ind.pb(ind);}
		ind++; it++;
	}
	vector<pl> p; //pairs {diameter projection index, distance to projection}
	REP(i,0,N)
	{
		ll val1 = m[(d1[i]-d2[i]+D)/2LL]; 
		ll val2 = (d1[i]+d2[i]-D)/2LL;
		p.pb({val1,val2});
	}
	vector<ll> oc; REP(i,0,s.size()) {oc.pb(0LL);}
	REP(i,0,N) {oc[p[i].ff]++;}
	ll hub = poss_ind[0];
	ll S = s.size();
	ll sum1,sum2;
	if(poss_ind.size()==2)
	{
		sum1=0LL;sum2=0LL;
		REP(i,poss_ind[0]+1,S) {sum1+=oc[i];}
		REP(i,0,poss_ind[1]) {sum2+=oc[i];}
		if(2*sum1==N) {return R;}
		else if(2*sum1>N) {hub=poss_ind[1];}
	}
	sum1=0LL;sum2=0LL;
	REP(i,0,hub) {sum1+=oc[i];} REP(i,hub+1,S) {sum2+=oc[i];}
	if(2*sum1>N || 2*sum2>N || 2*(oc[hub]-1)>N) {return -R;}
	return R;
}

Compilation message (stderr)

towns.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
towns.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:52:59: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   52 |  vector<ll> d0; d0.pb(0); REP(i,1,N) {d0.pb(getDistance(0,i));}
      |                                                           ^
towns.cpp:55:59: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   55 |  REP(i,0,N) {if(i==A) {d1.pb(0);} else {d1.pb(getDistance(A,i));}}
      |                                                           ^
towns.cpp:55:61: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   55 |  REP(i,0,N) {if(i==A) {d1.pb(0);} else {d1.pb(getDistance(A,i));}}
      |                                                             ^
towns.cpp:58:59: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   58 |  REP(i,0,N) {if(i==B) {d2.pb(0);} else {d2.pb(getDistance(B,i));}}
      |                                                           ^
towns.cpp:58:61: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   58 |  REP(i,0,N) {if(i==B) {d2.pb(0);} else {d2.pb(getDistance(B,i));}}
      |                                                             ^
towns.cpp:91:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   if(2*sum1==N) {return R;}
      |                         ^
towns.cpp:96:54: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   96 |  if(2*sum1>N || 2*sum2>N || 2*(oc[hub]-1)>N) {return -R;}
      |                                                      ^~
towns.cpp:97:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   97 |  return R;
      |         ^
towns.cpp:49:28: warning: unused parameter 'sub' [-Wunused-parameter]
   49 | int hubDistance(int N, int sub)
      |                        ~~~~^~~

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