C11CAVE - Hang động
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#include<algorithm>
#define MAX 500500
using namespace std;
int u[MAX];
int d[MAX];
int hu[MAX];
int hd[MAX];
int mu,md;
int n,h,ru,rd;
int i;
int b,c;
int main(void)
{
scanf("%d",&n);
scanf("%d",&h);
md=-1;
mu=-1;
for (i=1;i<=n/2;i=i+1)
{
scanf("%d",&d[i]);
scanf("%d",&u[i]);
if (d[i]>md) md=d[i];
if (u[i]>mu) mu=u[i];
}
sort(&d[1],&d[n/2+1]);
sort(&u[1],&u[n/2+1]);
for (i=n/2;i>=1;i=i-1)
{
hu[u[i]]=i;
hd[d[i]]=i;
}
for (i=mu;i>=1;i=i-1)
if (hu[i]==0) hu[i]=hu[i+1];
for (i=md;i>=1;i=i-1)
if (hd[i]==0) hd[i]=hd[i+1];
b=n+1;c=0;
for (i=1;i<=h;i=i+1)
{
if (i>md) rd=0;
else rd=n/2-hd[i]+1;
if (h-i+1>mu) ru=0;
else ru=n/2-hu[h-i+1]+1;
if (ru+rd==b)
{
c++;
continue;
}
if (ru+rd<b)
{
b=ru+rd;
c=1;
continue;
}
}
printf("%d %d",b,c);
}