Cod sursa(job #349386)

Utilizator Teodor94Teodor Plop Teodor94 Data 19 septembrie 2009 12:13:43
Problema Cautare binara Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
int a[1<<17];
int n,y,x;

int functie1 (int x)
{
	int i,pas;
	for (pas=1; pas<=n; pas<<=1);  // 2^n
	for (i=0; pas; pas>>=1)
		if (i+pas<=n && a[i+pas]<=x) 
			i+=pas;
	return i;
}
int functie0 (int x)
{
	int i,pas;
	for (pas=1; pas<=n; pas<<=1);  // 2^n
	for (i=0;pas;pas>>=1)
		if (i+pas<=n && a[i+pas]<=x) 
			i+=pas;
	if (a[i]!=x) return -1;
	return i;
}
int functie2 (int x)
{
	int i,pas;
	--x;
	for (pas=1;pas<=n;pas<<=1); // 2^n
	for (i=0;pas;pas>>=1)
		if (i+pas<=n && a[i+pas]<=x) 
			i+=pas;
	return 1+i;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
    int i;
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	int m;
	scanf("%d",&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		if (x==0) 
		{
			printf("%d\n",functie0(y));
		}
		else 
			if (x==1) 
			{
				printf("%d\n",functie1(y));
			}
			else
			{
				printf("%d\n",functie2(y));
			}
	}
	return 0;
}