Submission #105187

#	Time	Username	Problem	Language	Result	Execution time	Memory
105187		CaroLinda	Towns (IOI15_towns)	C++14	35 / 100	30 ms	432 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
 
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define ff first
#define ss second
#define pii pair<int,int>
#define MAXN 120
 
const int inf = 1e9 + 5 ; 
 
using namespace std;
 
//
int N  , A , B  , R , man;
int perp[MAXN] ;
int d[MAXN][MAXN] ;
//
void query( int x )
{ lp(i,0,N) d[x][i] = getDistance(x,i) ;}

int findMax( int x )
{ return max_element(d[x] , d[x] + N) - d[x] ; }

int findPerpendicular( int x )
{ return (d[A][x] + d[B][x] - d[A][B])/2 ; }

int findRadio()
{
	int ans = inf ;
	lp(i,0,N)
	{
		int k = max( d[A][i] , d[B][i] ) - perp[i] ;
		int Man = d[A][i] > d[B][i] ? A : B ;
		if( k < ans ) ans = k , man = Man ;
	}
	return ans ;
}

int sub4()
{
	int l = 0 , r = 0 , mid = 0  ;
	lp(i,0,N)
	{
		int k = d[man][i] - perp[i] ;
		if( k < R ) l ++ ;
		else if ( k > R ) r ++ ;
		else mid ++ ;
	}
	if(l>N/2 or r > N/2 or mid > N/2) return -R ;
	return R ;
}

int hubDistance( int n , int sub)
{
	N = n ;
	query(0) ;
	A = findMax(0) ;
	query(A) ;
	B = findMax(A) ;
	query(B) ;
	lp(i,0,n) perp[i] = findPerpendicular(i) ;
	R = findRadio() ;
	if( sub < 3 ) return R ;
	if( sub == 4 ) return sub4() ;
}

Compilation message (stderr)

towns.cpp: In function 'int findMax(int)':
towns.cpp:23:39: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
 { return max_element(d[x] , d[x] + N) - d[x] ; }
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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