Cod sursa(job #788291)

Utilizator misinoonisim necula misino Data 14 septembrie 2012 14:27:07
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 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;
bool 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]=1;
}
else
{m1++;
m[m1]=i;
s1-=v[i];
a[i]=0;
}
}
while(s1!=s)
{if(s1>s)
{x=rand()%p1+1;
s1-=(2*v[p[x]]);
--p1;
++m1;
m[m1]=p[x];
a[p[x]]=0;
swap(p[p1+1],p[x]);

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