Cod sursa(job #880049)
Utilizator | Data | 16 februarie 2013 10:51:53 | |
---|---|---|---|
Problema | Cautare binara | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.84 kb |
#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main()
{
int m,n,a,b,x,v[100001],p1,p2,p3,z,t,i;
f>>n;
p1=p2=-1;
for(i=1;i<=n;++i)
f>>v[i];
f>>m;
for(i=1;i<=m;++i)
{
f>>t>>z;
p1=-1;
p2=-1;
p3=n+1;
if(t%3==0)
{
a=1;
b=n;
x=(a+b)/2;
while(a<=b)
{
if(v[x]==z)
{
if(x>p1)p1=x;
a=x+1;
}
else
{
if(v[x]<z)a=x+1;
else b=x-1;
}
x=(a+b)/2;
}
g<<p1<<endl;
}
else
{
if(t%3==1)
{
a=1;
b=n;
x=(a+b)/2;
while(a<=b)
{
if(v[x]<=z)
{
if(x>p2)p2=x;
a=x+1;
}
else
{
if(v[x]<z)a=x+1;
else b=x-1;
}
x=(a+b)/2;
}
g<<p2<<endl;
}
else
{
a=1;
b=n;
x=(a+b)/2;
while(a<=b)
{
if(v[x]>=z)
{
if(x<p3)p3=x;
b=x-1;
}
else a=x+1;
x=(a+b)/2;
}
g<<p3<<endl;
}
}
}
f.close();
g.close();
return 0;
}