Submission #126103

#	Time	Username	Problem	Language	Result	Execution time	Memory
126103		baluteshih	Towns (IOI15_towns)	C++14	35 / 100	22 ms	376 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int INF=1e9;

int hubDistance(int N, int sub)
{
	vector<int> dis(N,0),a(N,0),b(N,0);
	int x,y,R=INF,RR;
	for(int i=1;i<N;++i)
		dis[i]=getDistance(0,i);
	x=max_element(ALL(dis))-dis.begin();
	for(int i=0;i<N;++i)
		if(i!=x)
			a[i]=getDistance(x,i);
	y=max_element(ALL(a))-a.begin();
	for(int i=0;i<N;++i)
		if(i!=y)
			b[i]=getDistance(y,i);
	for(int i=0;i<N;++i)
		R=min(R,abs(a[i]-b[i]));
	RR=(a[y]+R)/2;
	if(sub==1||sub==2||sub==4)
	{
		int cnt[3]={};
		for(int i=0;i<N;++i)
			if(abs(a[i]-b[i])==R) ++cnt[0];
			else if(a[i]<b[i]) ++cnt[1];
			else ++cnt[2];
		if(cnt[0]<=N/2&&cnt[1]<=N/2&&cnt[2]<=N/2) return RR;
		return -RR;
	}
	else
	{
		vector<int> chk;
		int cnt[3]={};
		for(int i=0;i<N;++i)
			if(abs(a[i]-b[i])==R) chk.pb(i);
			else if(a[i]<b[i]) ++cnt[1];
			else ++cnt[2];
		if(cnt[1]>N/2&&cnt[2]>N/2) return RR;
		while(chk.size())
		{
			int t=0;
			vector<int> nxt;
			for(int i:chk)
				if(getDistance(i,chk[0])<a[chk[0]]-RR+a[i]-RR)
					++t;
				else
					nxt.pb(i);
			if(t>N/2) return RR;
			nxt.swap(chk);
		}
		return RR;
	}
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:24:25: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
  x=max_element(ALL(dis))-dis.begin();
    ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:28:23: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
  y=max_element(ALL(a))-a.begin();
    ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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