제출 #1313598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313598		activedeltorre	도시들 (IOI15_towns)	C++20	25 / 100	9 ms	452 KiB

towns

#include "towns.h"
using namespace std;
#include <map>
#include <cmath>
#include <algorithm>
#include <iostream> 
int rez[225][5];
int getmax(int n,int b,int id)
{
    int best=-1,can=0;
    for(int i=0;i<n;i++)
    {
        rez[i][id]=getDistance(b,i);
        if(rez[i][id]>best)
        {
            best=rez[i][id];
            can=i;
        }
    }
    return can;
}
map<int,int>mp;
int hubDistance(int N, int sub) {
    mp.clear();
    int d1=getmax(N,1,0);
    int d2=getmax(N,d1,1);
    int d3=getmax(N,d2,2);
    int dab=rez[d2][1];
    int minim=100000000;
    for(int i=0;i<N;i++)
    {
        if(i!=d1 && i!=d2)
        {
            int distodim=(rez[i][1]+rez[i][2]-dab)/2;
            int x=(rez[i][1]-distodim);
            int y=(rez[i][2]-distodim);
            int diff=x-y;
            mp[diff]++;
            minim=min(minim,abs(diff));
        }
    }
    int prefix=1;
    int semn=-1;
    int r=(dab+minim)/2;
    int nmax=N/2;
    for(auto it:mp)
    {
        if(abs(it.first)==(minim))
        {
            if(it.second<=nmax && prefix<=nmax && N-prefix-it.second<=nmax)
            {
                semn=1;
            }
        }
        prefix=prefix+it.second;
    }
    if(sub==2)
        return r*semn;
	else
        return r;
}

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