oj.uz

Submission #105184

# Submission time Handle Problem Language Result Execution time Memory
105184 2019-04-10T22:58:32 Z CaroLinda Towns (IOI15_towns) C++14
25 / 100
 38 ms 932 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 17 ms 896 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 23 ms 932 KB Output is correct
5 Correct 17 ms 896 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct
2 Correct 14 ms 896 KB Output is correct
3 Correct 21 ms 896 KB Output is correct
4 Correct 18 ms 896 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 384 KB Output isn't correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -