Cod sursa(job #599185)

Utilizator stefanzzzStefan Popa stefanzzz Data 28 iunie 2011 11:42:02
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream.h>

int n;
long s,v[2][171701],i,j,k,a[101],cnt,x;

void Qsort(long p, long q);
long Divide(long p, long q);
long cauta(long t, long st, long dr);
void afisare(long m);

main(){
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	scanf("%d%ld", &n, &s);
	for(i=1;i<=n;i++)
		scanf("%ld", &a[i]);
	for(i=1;i<=n;i++){
		for(j=i;j<=n;j++){
			for(k=j;k<=n;k++){
				v[0][++cnt]=a[i]+a[j]+a[k];
				v[1][cnt]=cnt;}}}
	Qsort(1,cnt);
	for(i=1;v[0][cnt]<s-v[0][i];i++);
	for(i;v[0][i]<=(s+1)/2;i++){
		x=cauta(s-v[0][i],i,cnt);
		if(x){
			afisare(v[1][i]);
			afisare(v[1][x]);
			return 0;}}
	printf("-1");
}
		
			
	

void Qsort(long p, long q){
	long m;
	m=Divide(p,q);
	if(m<q-1)
		Qsort(m+1, q);
	if(m>p+1)
		Qsort(p,m-1);}

long Divide(long p, long q){
	long st=p, dr=q, x=v[0][p],y=v[1][p];
	while(st<dr){
		while(st<dr&&x<=v[0][dr])
			dr--;
		v[0][st]=v[0][dr];
		v[1][st]=v[1][dr];
		while(st<dr&&x>=v[0][st])
			st++;
		v[0][dr]=v[0][st];
		v[1][dr]=v[1][st];}
	v[0][st]=x;
	v[1][st]=y;
	return st;}

	
		
long cauta(long t,long st, long dr){
	if(st>dr)
		return 0;
	long m=(st+dr)/2;
	if(t==v[0][m])
		return m;
	if(v[0][m]>t)
		return cauta(t,st,m-1);
	return cauta(t,m+1,dr);}
		
	
void afisare(long m){
	int d=0;
	while(m>(n-d)*(n+1-d)/2){
		m-=(n-d)*(n+1-d)/2;
		d++;}
	printf("%ld ", a[d+1]);
	while(m>n-d){
		m-=n-d;
		d++;}
	printf("%ld %ld ", a[d+1], a[d+m]);
}