Submission #133748

#	Time	Username	Problem	Language	Result	Execution time	Memory
133748		MAMBA	Towns (IOI15_towns)	C++17	35 / 100	21 ms	376 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j; i < k; i++)

typedef long long ll;

template<class S, class T> 
inline bool smax(S &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

const int MAXN = 1e3;

ll D1[MAXN], D2[MAXN], f[MAXN], z[MAXN];

int hubDistance(int N, int sub) {

	int r1 = 0;
	ll d = 0;
	rep(i , 1 , N) 
		if (smax(d , getDistance(0 , i)))
			r1 = i;

	rep(i , 0 , N)
		D1[i] = getDistance(r1 , i);
	int r2 = max_element(D1 , D1 + N) - D1;

	rep(i , 0 , N) 
		D2[i] = getDistance(r2 , i);

	ll limit = D1[r2];


	rep(i , 0 , N) 
		f[i] = (limit + D1[i] - D2[i]) / 2;

	sort(f , f + N);

	ll R = limit;
	rep(i , 0 , N) 
		R = min(R , max(f[i] , limit - f[i]));

	if (sub <= 2) return R;


	// DONE DONE DONE DONE DONE 


	int i1 = 0,  i2 = 0;

	int j1 = 0, j2 = 0;

	rep(i , 0 , N) {
		if (f[i] == R) i2++;
		if (f[i] == limit - R) i1++;
		if (f[i] < limit - R) j1++;
		if (f[i] > R) j2++;
	}

	int n2 = N / 2;
	if (sub == 4) {
		if (j1 <= n2 && i1 <= n2 && (N - j1 - i1) <= n2)
			return R;
		if (j2 <= n2 && i2 <= n2 && (N - j2 - i2) <= n2)
			return R;
		return -R;
	}

	// DONE DONE DONE DONE DONE DONE DONE DONE 


	rep(i , 0 , N) {
		z[i] = (limit + D1[i] - D2[i]) / 2;
		f[i] = D1[i] - z[i];
	}

	auto check = [&](int g) -> bool {
		int cnt = 0;
		int last = -1;
		rep(i , 0 , N)
			if (z[i] == g) {
				if (last == -1 || getDistance(i , last) == f[i] + f[last]) {
					cnt--;
					if (cnt <= 0) {
						cnt = 1;
						last = i;
					}
				}
				else 
					cnt++;
			}
		cnt = 0;
		rep(i , 0 , N)
			if (z[i] == g && getDistance(last , i) != f[i] + f[last])
				cnt++;
		return cnt <= n2;
	};


	if (limit == 2*R) {
		if (j1 <= n2 && j2 <= n2)
			if (check(R))
				return R;
		return -R;
	}
	else if (j2 + i2 <= n2) {
		if (check(limit - R))
			return R;
		return -R;
	}
	else if (i1 + j1 <= n2) {
		if (check(R))
			return R;
		return -R;
	}

	return -R;


}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:33:36: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  int r2 = max_element(D1 , D1 + N) - D1;
           ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:50:23: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  if (sub <= 2) return R;
                       ^
towns.cpp:70:11: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    return R;
           ^
towns.cpp:72:11: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    return R;
           ^
towns.cpp:73:10: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return -R;
          ^~
towns.cpp:109:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    if (check(R))
               ^
towns.cpp:110:12: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return R;
            ^
towns.cpp:111:10: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return -R;
          ^~
towns.cpp:114:19: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   if (check(limit - R))
             ~~~~~~^~~
towns.cpp:115:11: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    return R;
           ^
towns.cpp:116:10: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return -R;
          ^~
towns.cpp:119:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   if (check(R))
              ^
towns.cpp:120:11: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    return R;
           ^
towns.cpp:121:10: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return -R;
          ^~
towns.cpp:124:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return -R;
         ^~

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