Codeforces Round #271 (Div. 2) 474B Worms

Solution to Codeforces Round #271 (Div. 2) 474B Worms With Explanation

       Kindly comment if you have any other best solution or found any errors in my program.

Explanation:

        In this problem, all the worms in the packs are numbered consecutively. You have to find, in which pack the 'q'th worm resides. Binary search technique should be used as the bubble sort will give you a TLE.

Steps:

• Get the number of worms in each pack in an array.
• While getting worms in each pack maintain the sum of the all the worms till that particular pack in another array s[].
• Then sort array 'S' as the binary search works only on a sorted array.
• Then get the label of the juicy worm and search it in the array 'S' using binary search.
• Repeat until finish searching all the juicy worms in the array.

Program:

//    Accepted                                                                            592ms                             800KB

#include<iostream>
using namespace std;
int binarysearch(int low,int high,int q,int s[])
{
    int index;
    if(low>high)
        index=0;
    else
        {
    int mid=(low+high)/2;
    if(q==s[mid])
        index=mid+1;
    else{
            if(q<s[0])
               return 1;
    if((q>s[mid])&&(q<s[mid+1]))
        index=mid+2;
    else if(q<s[mid])
        index=binarysearch(low,mid-1,q,s);
    else
        index=binarysearch(mid+1,high,q,s);
    }
    }
    return index;
}
int main()
{
    int n,m;
    cin>>n;
    int a[n],sum=0,s[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum=sum+a[i];
        s[i]=sum;
    }
    cin>>m;

   while(m--)
   {
       int q;
       cin>>q;
       cout<<binarysearch(0,n,q,s)<<endl;;
   }
   return 0;
}