제출 #1085374

#제출 시각아이디문제언어결과실행 시간메모리
1085374guagua0407도시들 (IOI15_towns)C++17
25 / 100
16 ms1116 KiB
#include "towns.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int hubDistance(int N, int sub) { int n=N; vector<int> dis(n); for(int i=0;i<n;i++){ dis[i]=getDistance(0,i); } int x=max_element(all(dis))-dis.begin(); for(int i=0;i<n;i++){ dis[i]=getDistance(x,i); } int y=max_element(all(dis))-dis.begin(); vector<int> dis2(n); for(int i=0;i<n;i++){ dis2[i]=getDistance(y,i); } vector<int> vec; for(int i=0;i<n;i++){ vec.push_back(dis[i]-(dis[i]+dis2[i]-dis[y])/2); } sort(all(vec)); int R=dis[y]; int ans=R; for(auto v:vec){ ans=min(ans,max(v,R-v)); } map<int,int> mp; for(auto v:vec){ mp[v]++; } bool tf=false; int pre=0; for(auto v:mp){ if(max(v.f,R-v.f)==ans){ int mx=max({pre,v.s,n-pre-v.s}); if(mx<=n/2){ tf=true; } } pre+=v.s; } if(!tf){ pre=0; for(auto v:mp){ if(max(v.f,R-v.f)==ans){ int mx=max({pre,v.s,n-pre-v.s}); if(mx<=n/2){ tf=true; } else if(v.s>n/2){ mt19937 rng(time(NULL)); if(abs((int)rng())%2==0) tf=true; } } pre+=v.s; } } return (tf?ans:-ans); }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:17:32: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   17 |     int x=max_element(all(dis))-dis.begin();
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:21:32: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   21 |     int y=max_element(all(dis))-dis.begin();
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:11:28: warning: unused parameter 'sub' [-Wunused-parameter]
   11 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...