Cod sursa(job #749100)

Utilizator matei_cChristescu Matei matei_c Data 15 mai 2012 19:32:02
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include<cstdio>
#include<cstdlib>
using namespace std;

const int MAX_N = 50001 ;

int n ;
int a[MAX_N] ;
int plus[MAX_N],minus[MAX_N] ;
char sol[MAX_N] ;
long long sum,suma ;

int main()
{
	
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	
	int nrp = 0 ;
	int nrm = 0 ;
	scanf("%d%lld",&n,&suma);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		int x = rand() % 2 ;
		if(x == 1)
		{
            plus[++nrp] = i ;
            sum = (long long)(sum+a[i]) ;
            sol[i] = '+' ;
        }
		else
		{
            minus[++nrm] = i ;
            sum = (long long)(sum-a[i]) ;
            sol[i] = '-' ;
		}	
	}	
	
	while(sum != suma)
	{
        if (sum < suma)
		{
            int x = rand() % nrm + 1 ;
            plus[++nrp] = minus[x] ;
            minus[x] = minus[nrm] ;
            --nrm ;
            sum = (long long)(sum + 2 * a[plus[nrp]]) ;
            sol[plus[nrp]] = '+' ;
        }
		else
		{
            int x = rand() % nrp + 1 ;
            minus[++nrm] = plus[x] ;
            plus[x] = plus[nrp] ;
            --nrp ;
            sum = (long long)(sum - 2 * a[minus[nrm]]) ;
            sol[minus[nrm]] = '-' ;
        }
    }
	
	for(int i=1;i<=n;++i)
		printf("%c",sol[i]);
	printf("\n");
	
	return 0;
	
}



















/*


#include <fstream>
#include <cstdlib>
#include <ctime>
#define nmax 50005

using namespace std;

ifstream f("semne.in");
ofstream g("semne.out");

void citeste(){

    f >> n >> s;
    for(int i=1; i<=n; i++){
        f >> a[i];
        int x = rand()%2;

        if (x){
            Plus[++nr_p] = i;
            s2 += a[i]*1LL;
            rez[i] = '+';
        }else {
            Minus[++nr_m] = i;
            s2 -= a[i]*1LL;
            rez[i] = '-';
        }
    }

}

void rezolva(){


    for(; s2 != s; ){
        if (s2 < s){//daca suma act e mai mica atunci modific un minus in plus
            int x = rand()%nr_m+1;
            Plus[++nr_p] = Minus[x];
            Minus[x] = Minus[nr_m];
            --nr_m;
            s2 += 1LL*2*a[ Plus[nr_p] ];//adaug la suma de 2 ori valoarea(fiindca inainte l`am scazut)
            rez[ Plus[nr_p] ] = '+';
        }else {
            int x = rand()%nr_p+1;
            Minus[++nr_m] = Plus[x];
            Plus[x] = Plus[nr_p];
            --nr_p;
            s2 -= 1LL*2*a[ Minus[nr_m] ];
            rez[ Minus[nr_m] ] = '-';
        }
    }

}

void scrie(){

    for(int i=1; i<=n; i++) g << rez[i];
    g << "\n";

}

int main(){

    srand((unsigned)time(NULL));

    citeste();
    rezolva();
    scrie();

    f.close();
    g.close();

    return 0;

}

*/