Cod sursa(job #267727)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 27 februarie 2009 22:23:14
Problema Stramosi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>

long n,m,k;
struct stramos{
long ind,str;};

stramos v[2500],a[3000];

void cit()
{scanf("%d %d",&n,&m);
 long i;
 for (i=1;i<=n;i++)
  {
	scanf("%ld ",&v[i].str);
	v[i].ind=i;
  }
 for (i=1;i<=m;i++)
  {
	scanf("%ld %ld",&a[i].ind,&a[i].str);
  }}

void poz(long li, long ls, long &k, stramos v[2500])
{long i=li,j=ls,i1=0,j1=-1,aux;
 stramos c;
 while (i<j)
  {
	if (v[i].ind>v[j].ind)
	 {
		c=v[j]; v[j]=v[i]; v[i]=c;
		aux=i1; i1=-j1; j1=-aux;
	 }
	i+=i1;
	j+=j1;
  }
 k=i;}

void quick(long li, long ls)
{if (li<ls)
  {
	poz(li,ls,k,v);
	quick(li,k-1);
	quick(k+1,ls);
  }}

long bi_s(long val)
{long i,step;
 for (step=1;step<n;step<<=1);
 for (i=0;step;step>>=1)
	if (i+step<n && v[i+step].ind<=val) i+=step;
 return v[i].ind;}

void det()
{long p,q;
 for (long i=1;i<=m;i++)
  {
	for (long j=1;j<=a[i].str;j++)	q=bi_s(v[q].str);
	printf("%d\n",q);
  }}

int main()
{freopen("stramosi.in","r",stdin);
 freopen("stramosi.out","w",stdout);
 cit();
/* quick(1,n);*/
 det();
 return 0;}