Submission #264747

#	Time	Username	Problem	Language	Result	Execution time	Memory
264747		patrikpavic2	Towns (IOI15_towns)	C++17	13 / 100	26 ms	896 KiB

towns

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  towns
* score: 13.0
* date:  2019-06-23 12:02:09.479096
*/
#include "towns.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>

#define PB push_back
#define X first
#define Y second

using namespace std;

const int N = 505;
const int INF = 0x3f3f3f3f;

typedef pair < int, int > pii;
typedef vector < pii > vp;
typedef vector < int > vi;

int dis[3][N], l = 0, r = 0, off[N], koj;
map < int, vi > mp;

bool same(int i,int j){
	return getDistance(i, j) < off[i] + off[j];
}

int calc(vi v){
	if(v.size() == 0) return 0;
	int st = v[0], cur = 1;
	for(int x : v){
		if(cur == 0) st = x;
		if(same(x, st)) cur++;
		else cur--;
	}
	return st;
}

int cnt(vi v,int x){
	if(v.size() == 0) return 0;
	int ret = 0;
	for(int y : v)
		ret += same(x, y);
	return ret;
}

int hubDistance(int n, int sub) {
	memset(dis, 0, sizeof(dis));
	l = 0; r = 0; mp.clear();
	for(int i = 0;i < n;i++){
		dis[0][i] = getDistance(l, i);
		if(dis[0][i] > dis[0][r]) r = i;
	}
	for(int i = 0;i < n;i++){
		dis[1][i] = getDistance(r, i);
		if(dis[1][i] > dis[1][l]) l = i;
	}
	for(int i = 0;i < n;i++){
		dis[2][i] = getDistance(l, i);
	}
	int dim = dis[1][l];
	//printf("%d\n", dim);
	int ans = INF;
	for(int i = 0;i < n;i++){
		int of = (dis[1][i] + dis[2][i] - dim) / 2;
		mp[dis[1][i] - of].PB(i);
		off[i] = of;
		//printf("%d\n", dis[1][i] - of);
		ans = min(ans, max(dis[1][i], dis[2][i]) - of);
	}
	int ima = 0, ccnt = 0;
	for(pair < int, vi > x : mp){
		if(max(x.X, dim - x.X) == ans){
			int pos = 1;
			if(ccnt > n / 2 ) 
				pos = 0;
			if(cnt(x.Y, calc(x.Y)) > n / 2)
				pos = 0;
			if(n - ccnt - x.Y.size() > n / 2)
				pos = 0;
			ima += pos;
		}
		ccnt += (int)x.Y.size();
	}
	if(!ima) return -ans;
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:87:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |    if(n - ccnt - x.Y.size() > n / 2)
      |       ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:55:28: warning: unused parameter 'sub' [-Wunused-parameter]
   55 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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