Cod sursa(job #333932)

Utilizator MciprianMMciprianM MciprianM Data 24 iulie 2009 17:52:01
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>

#include<cstdlib>
#include<ctime>
using namespace std;
#define maxn 50001
long long s;
int n, a[maxn];
int a1[maxn], a2[maxn];
char semne[maxn];
int main(){
	int i, i1, i2,va,aux;
	long long s1, s2;
	s1=s2=0;
	ifstream f("semne.in");
	f>>n>>s;
	for(i=0;i<n;i++)
		f>>a[i];
	f.close();
	for(i=i1=i2=0;i<n;i++)
		if(s1<s2){
			s1+=a[i];
			a1[i1++]=i;
		}
		else{
			s2+=a[i];
			a2[i2++]=i;
		}
	srand(time(0));
	while(s2-s1!=s){
		if(s2-s1<s){
			va=rand()%i1;
			aux=a1[i1];
			a1[i1]=a1[va];
			a1[va]=aux;
			s1-=a[a1[i1]];
			s2+=a[a1[i1]];
			a2[i2++]=a1[i1];
			i1--;
		}
		else{
			va=rand()%i2;
			aux=a2[i2];
			a2[i2]=a2[va];
			a2[va]=aux;
			s2-=a[a2[i2]];
			s1+=a[a2[i2]];
			a1[i1++]=a2[i2];
			i2--;
		}
	}
	for(i=0;i<i1;i++)
		semne[a1[i]]='-';
	for(i=0;i<i2;i++)
		semne[a2[i]]='+';
	ofstream g("semne.out");
	g<<semne<<'\n';
	g.close();
	return 0;
}