Submission #105184

#	Time	Username	Problem	Language	Result	Execution time	Memory
105184		CaroLinda	Towns (IOI15_towns)	C++14	25 / 100	38 ms	932 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;
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)
		ans = min( ans , max( d[A][i] , d[B][i] ) - perp[i] ) ;
	return ans ;
}

int sub4()
{
	int l = 0 , r = 0 , mid = 0;
	lp(i,0,N)
	{
		if( d[A][i] + d[B][i] > d[A][B] ) mid++ ;
		else if( d[A][i] > d[B][i] ) l ++ ;
		else r ++ ;
	}
	
	if( r > N/2 or l > 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:24: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:63: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: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39