oj.uz

Submission #133742

# Submission time Handle Problem Language Result Execution time Memory
133742 2019-07-21T09:17:20 Z MAMBA Towns (IOI15_towns) C++17
35 / 100
 21 ms 504 KB 
#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;


	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;
	}


	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;
	}
	if (j2 + i2 <= n2) {
		if (check(limit - R))
			return R;
		return -R;
	}
	if (i1 + j1 <= n2) {
		if (check(R))
			return R;
		return -R;
	}

	return -R;


}

Compilation message

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:67:11: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    return R;
           ^
towns.cpp:69:11: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    return R;
           ^
towns.cpp:70:10: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return -R;
          ^~
towns.cpp:104:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    if (check(R))
               ^
towns.cpp:105:12: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return R;
            ^
towns.cpp:106:10: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return -R;
          ^~
towns.cpp:109:19: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   if (check(limit - R))
             ~~~~~~^~~
towns.cpp:110:11: 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:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   if (check(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:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return -R;
         ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 376 KB Output is correct
2 Correct 16 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 20 ms 376 KB Output is correct
5 Correct 20 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 376 KB Output is correct
2 Correct 16 ms 416 KB Output is correct
3 Correct 21 ms 376 KB Output is correct
4 Correct 20 ms 376 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 504 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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