제출 #288571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288571		amoo_safar	도시들 (IOI15_towns)	C++17	25 / 100	31 ms	512 KiB

towns

#include "towns.h"

#include <bits/stdc++.h>

using namespace std;


const int N = 200;
int d0[N], d1[N], D[N], val[N], disth[N];

typedef pair<int, int> pii;

bool Same(int u, int v){
	if(u == v) return true;
	if(disth[u] + disth[v] == getDistance(u, v)) return false; 
	return true;
}

int hubDistance(int n, int sub) {
	assert(sub >= 0);
	d0[0] = 0;
	for(int i = 1; i < n; i++)
		d0[i] = getDistance(0, i);
	int mx = max_element(d0, d0 + n) - d0;

	d1[0] = d0[mx];
	for(int i = 1; i < n; i++)
		d1[i] = (i == mx ? 0 : getDistance(i, mx));

	int dia = *max_element(d1, d1 + n);
	int R = 2000000;

	for(int i = 0; i < n; i++){
		int X = (d0[i] + d1[i] - d0[mx]) / 2;
		int P = d1[i] - X;
		R = min(R, max(P, dia - P));
		D[i] = X;
		val[i] = P;
	}
	if(sub <= 2) return R;
	//map<int, vector<int> > mp;
	
	vector<int> Hub, VH, VD;
	for(int i = 0; i < n; i++){
		if(R == max(val[i], dia - val[i])){
			Hub.push_back(val[i]);
		}
		VD.push_back(val[i]);
	}
	sort(Hub.begin(), Hub.end());
	Hub.resize(unique(Hub.begin(), Hub.end()) - Hub.begin());
	
	sort(VD.begin(), VD.end());
	assert(Hub.size() <= 2);

	for(auto x : Hub){
		int ls = lower_bound(VD.begin(), VD.end(), x) - VD.begin();
		int bg = n - (upper_bound(VD.begin(), VD.end(), x) - VD.begin());
		int mxx = max(ls, bg);
		if(mxx + mxx < n) VH.push_back(x);
		if(mxx + mxx == n) return R;
		
	}
	if(VH.empty()) return -R;
	assert(VH.size() == 1);

	int hb = VH[0];
	for(int i = 0; i < n; i++) disth[i] = abs(hb - val[i]) + D[i];
	
	vector<pii> PA;
	for(int i = 0; i + 1 < n; i += 2){
		if(Same(i, i + 1))
			PA.push_back({i, 2});
	}
	if(n & 1)
		PA.push_back({n - 1, 1});
	
	if(PA.empty()) return R;

	int la = PA[0].first, hp = PA[0].second;

	for(int i = 1; i < PA.size(); i++){
		if(hp == 0){
			la = PA[i].first;
			hp = PA[i].second;
			continue;
		}
		if(Same(PA[i].first, la)) hp += PA[i].second;
		else {
			hp -= PA[i].second;
			if(hp >= 0) continue;
			hp = -hp;
			la = PA[i].first;
		}
	}
	if(hp == 0) return R;

	int maj = la;
	int sam = 0;
	int all = 0;
	for(int i = 0; i < n; i++){
		if(Same(maj, PA[i].first)) sam += PA[i].second;
		all += PA[i].second;
		//if(Same(maj, i)) sam ++;
	}
	
	if(sam + sam > all) return -R;
	return R;
}

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:24:35: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   24 |  int mx = max_element(d0, d0 + n) - d0;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:57:49: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   57 |   int ls = lower_bound(VD.begin(), VD.end(), x) - VD.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:58:14: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   58 |   int bg = n - (upper_bound(VD.begin(), VD.end(), x) - VD.begin());
      |            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towns.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i = 1; i < PA.size(); i++){
      |                 ~~^~~~~~~~~~~

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