Tuesday, June 2, 2015

UVa - 10474 - Where is the Marble?

Problem Link: 10474 - Where is the Marble?
/****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
__________________________________________________________________________
######################  Ya-Seen Arafat(ACWizard) #########################
######################        UAP-CSE-33B        #########################
*************************************************************************/
#include <bits/stdc++.h>
using namespace std;

int main(){
    int low, high, mid, n, q, element, query, cs = 1;
    vector <int> numbers;
    while(scanf("%d %d", &n, &q) == 2){
        if(n == 0 && n == q)break;
        for(int i = 1; i <= n; i++)scanf("%d", &element), numbers.push_back(element);
        sort(numbers.begin(), numbers.end());
        printf("CASE# %d:\n", cs);cs++;
        for(int i = 1; i <= q; i++){
            scanf("%d", &query);
            int found = 0;
            low = 0, high = n-1;
            while(low <= high){
                mid = (low+high) / 2;
                if(numbers[mid] == query){
                    found = 1;break;
                }
                if(numbers[mid] > query)high = mid - 1;
                else if(numbers[mid] < query)low = mid + 1;
            }
            if(found){
                while(numbers[mid] == query)mid--;
                printf("%d found at %d\n", query, mid+2);
            }
            else printf("%d not found\n",  query);
        }
        numbers.clear();
    }
    return 0;
}

No comments:

Post a Comment