Cod sursa(job #196372)

Utilizator blasterzMircea Dima blasterz Data 26 iunie 2008 08:57:26
Problema Cautare binara Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#define DIM 8192

char ax[DIM+16];
int pz;

inline void cit(int &x)
{
    x=0;
    while(ax[pz]<'0' || ax[pz]>'9')
	if(++pz==DIM)fread(ax, 1, DIM, stdin),pz=0;
    while(ax[pz]>='0' && ax[pz]<='9')
    {
	x=x*10+ax[pz]-'0';
	if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;
    }
}

int a[100001];
int n, m;

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    cit(n);

    int i,cnt;
    for(i=1;i<=n;++i) cit(a[i]);
    cit(m);

    int t, x;
    while(m--)
    {
	cit(t); cit(x);
    

	if(t==0)
	{
	    for(i=1, cnt=(1<<18); cnt; cnt>>=1)
		if(i+cnt<=n)
		    if(a[i+cnt]<=x)i+=cnt;

	    if(a[i]==x) printf("%d\n", i);
	    else printf("-1\n");
	}

	if(t==1)
	{
	    for(i=1, cnt=(1<<18); cnt; cnt>>=1)
		if(i+cnt<=n)
		    if(a[i+cnt]<=x)i+=cnt;
	    printf("%d\n", i);
	}

	if(t==2)
	{
	    for(i=n, cnt=(1<<18); cnt; cnt>>=1)
		if(i-cnt>=1)
		    if(a[i-cnt]>=x)i-=cnt;
	    printf("%d\n", i);
	}



	


    }

    return 0;
}