Cod sursa(job #573955)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 6 aprilie 2011 18:22:49
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.74 kb
#include<fstream> 
using namespace std; 
ifstream fin("semne.in"); 
ofstream fout("semne.out"); 
long long sa,sb,s; 
int a[50000],b[50000],na,nb,n,x[50001],i; 
int main() 
{fin>>n>>s; 
na=n/2; 
nb=n-na; 
for(i=1;i<=n;i++) 
{fin>>x[i]; 
if(i<=na)    
{a[i]=i;    
sa+=x[i];
} 
else
{b[i-na]=i;    
sb+=x[i];
}
} 
while((sa-sb)!=s) 
{
while((sa-sb)>s) 
{
i=rand()%na+1; 
b[++nb]=a[i]; 
sa=sa-x[a[i]]; 
sb=sb+x[a[i]]; 
a[i]=a[na]; 
a[na]=0; 
--na;
} 
while((sa-sb)<s) 
{i=rand()%nb+1; 
a[++na]=b[i]; 
sa=sa+x[b[i]]; 
sb=sb-x[b[i]];    
b[i]=b[nb]; 
b[nb]=0;
--nb;
}
} 
for(i=1;i<=na;i++) 
x[a[i]]=0; 
for(i=1;i<=n;i++) 
if(x[i]==0) 
fout<<"+";   
else
fout<<"-";
fin.close();
fout.close();
return 0;
}