Source Code

Problem: 2010  User: yzhw 
Memory: 3136K  Time: 282MS 
Language: G++  Result: Accepted 

Source Code 
# include <cstdio>
using namespace std;
# include <algorithm>
# include <cstring>
int n,c,f;
struct node
{
   int s,c;
   int id;
}cows[100005],cowc[100005];
int rank[100005];
bool cmps(node a,node b)
{
    return a.s<b.s;
}
bool cmpc(node a,node b)
{
    return a.c<b.c;
}
int chk(int pos)
{
    int left=0,right=0,tf=f;
    bool mid=false;
    for(int i=0;i<c;i++)
      if(rank[cowc[i].id]<pos&&left<n/2)
         if(tf>=cowc[i].c)
            left++,tf-=cowc[i].c;
         else break;
      else if(rank[cowc[i].id]==pos&&!mid)
         if(tf>=cowc[i].c)
             mid=true,tf-=cowc[i].c;
         else  break;
      else if(rank[cowc[i].id]>pos&&right<n/2)
         if(tf>=cowc[i].c)
             right++,tf-=cowc[i].c;
         else break;
    if(left>=n/2&&right>=n/2&&mid) return 0;
    else if(left>=n/2) return 1;
    else if(right>=n/2) return -1;
    else if(left<n/2&&right<n/2) return -2;
}
int main()
{
    scanf("%d%d%d",&n,&c,&f);
    for(int i=0;i<c;i++)
    {
      scanf("%d%d",&cows[i].s,&cows[i].c);
      cows[i].id=i;
    }
    memcpy(cowc,cows,sizeof(cows));
    sort(cows,cows+c,cmps);
    sort(cowc,cowc+c,cmpc);
  /*  printf("sorted by s\n");
       for(int i=0;i<c;i++)
         printf("(%d,%d)\n",cows[i].id,cows[i].s);
    printf("\n");
    printf("sorted by c\n");
       for(int i=0;i<c;i++)
         printf("(%d,%d)\n",cowc[i].id,cowc[i].c);
    printf("\n");*/
    int s=n/2,e=c-1-n/2;
    for(int i=0;i<c;i++)
      rank[cows[i].id]=i;
    while(s<=e)
    {
       int mid=(s+e)/2;
       switch(chk(mid))
       {
          case -1:
               s=mid+1;
               break;
          case 1:
               e=mid-1;
               break;
          case 0:
               s=mid+1;
               break;
          case -2:
               printf("-1\n");
               return 0;
       };
    }
    if(chk(s-1)==0)
      printf("%d\n",cows[s-1].s);
    else
      printf("-1\n");
   //   system("pause");
      return 0;
}