Cod sursa(job #1149472)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 21 martie 2014 21:42:22
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
int a[50050];
bool semn[50050];
int semn1[50050];
int semn2[50050];

int main()
{
    srand(time(0));
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    int n,x,size1=0,size2=0;
    long long s=0,sf;
    scanf("%d%lld",&n,&sf);
    for(int i=1;i<=n;++i){
      scanf("%d",&a[i]);
      x=rand()%2;
      semn[i]=x;
      if(x==1) {
         s=s+a[i];
         semn1[++size1]=i;
      }
      else {
         s=s-a[i];
         semn2[++size2]=i;
      }
    }
    while(s!=sf){
       if(s>sf){
         x=rand()%(size1+1);
         semn[semn1[x]]=0;
         s=s-2*a[semn1[x]];
         semn2[++size2]=semn1[x];
         semn1[x]=semn1[size1];
         --size1;
       }
       else{
         x=rand()%(size2+1);
         semn[semn2[x]]=1;
         s=s+2*a[semn2[x]];
         semn1[++size1]=semn2[x];
         semn2[x]=semn2[size2];
         --size2;
       }
    }
    for(int i=1;i<=n;++i){
      if(semn[i]==1) printf("+");
      else printf("-");
    }
    return 0;
}