View Code of Problem 1093

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
struct node
{ int a,b;
}cow[200010];
node cow2[100010];
int n,c;
long long f;
bool cmp1(node a,node b)
{ if(a.a<b.a)
   return true;
  else
   if(a.a==b.a)
    return a.b<b.b;
  else
   return false;
}
bool cmp2(node a,node b)
{ return a.b<b.b;
}
bool solve(int x)
{ int i,k,value=cow[x].a,num1=0,num2=0,num3=0;
  long long sum=f-cow[x].b;
  for(i=1;i<=c;i++)
  { cow2[i].a=cow[i].a;
    cow2[i].b=cow[i].b;
  }
  cow2[x].a=cow2[c].a;
  cow2[x].b=cow2[c].b;
  sort(cow2+1,cow2+c,cmp2);
  for(i=1;i<c;i++)
  { if(cow2[i].a==value)
    { sum-=cow2[i].b;
      num3++;
    }
    else if(cow2[i].a<value && num1<n/2 && sum>=cow2[i].b)
    { sum-=cow2[i].b;
      num1++;
    }
    else if(cow2[i].a>value && num2<n/2 && sum>=cow2[i].b)
    { sum-=cow2[i].b;
      num2++;
    }
    if(num1+num2+num3>=n-1)
     return true;
  }
  return false;
}
int main()
{ int i,j,ans=-1;
  scanf("%d%d%I64d",&n,&c,&f);
  for(i=1;i<=c;i++)
   scanf("%d%d",&cow[i].a,&cow[i].b);
  sort(cow+1,cow+1+c,cmp1);
  int l=1,r=c,mi;
  while(l<=r)
  { mi=(l+r)/2;
    if(solve(mi))
    { ans=cow[mi].a;
      l=mi+1;
    }
    else
     r=mi-1;
  }
  if(ans!=-1)
   printf("%d\n",ans);
  else
   printf("-1\n");
}

Double click to view unformatted code.


Back to problem 1093