Cod sursa(job #788289)

Utilizator misinoonisim necula misino Data 14 septembrie 2012 14:22:27
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
FILE *f,*g;
int x,n,i,m1,p1,p[50001],m[50001],v[50001];
long long s,s1;
char a[50001];
int main()
{f=fopen("semne.in","r");
g=fopen("semne.out","w");
fscanf(f,"%d%Ld",&n,&s);
for(i=1;i<=n;++i)
	fscanf(f,"%d",&v[i]);
for(i=1;i<=n;++i)
{x=rand()%2;
if(x)
{p1++;
p[p1]=i;
s1+=v[i];
a[i]='+';
}
else
{m1++;
m[m1]=i;
s1-=v[i];
a[i]='-';
}
}
while(s1!=s)
{if(s1>s)
{x=rand()%p1+1;
s1-=(2*v[p[x]]);
--p1;
++m1;
m[m1]=p[x];
a[p[x]]='-';
swap(p[p1+1],p[x]);

}
else
{x=rand()%m1+1;
s1+=(2*v[m[x]]);
p[++p1]=m[x];
a[m[x]]='+';
swap(m[m1--],m[x]);
}
}
for(i=1;i<=n;++i)
	fprintf(g,"%c",a[i]);
return 0;
}