Cod sursa(job #1735167)

Utilizator cella.florescuCella Florescu cella.florescu Data 29 iulie 2016 10:49:50
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.05 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define MAXN 50000

using namespace std;

struct numar{
  int val, pos;
} plu[MAXN], minu[MAXN];

char sol[MAXN];

int main()
{
    FILE *fin, *fout;
    long long sum, s;
    int n, i, nplus, nminus;
    srand(time(NULL));
    fin=fopen("semne.in", "r");
    fscanf(fin, "%d%lld", &n, &s);
    sum=0LL; nminus=0;
    for(i=0; i<n; i++){
      fscanf(fin, "%d", &plu[i].val);
      plu[i].pos=i;
      sum+=1LL*plu[i].val;
    }
    fclose(fin);
    nplus=n;
    while(s!=sum)
      if(s<sum){
        i=rand()%nplus;
        sum-=2LL*plu[i].val;
        minu[nminus++]=plu[i];
        plu[i]=plu[--nplus];
      } else{
        i=rand()%nminus;
        sum+=2LL*minu[i].val;
        plu[nplus++]=minu[i];
        minu[i]=minu[--nminus];
      }
    for(i=0; i<nplus; i++)
      sol[plu[i].pos]='+';
    fout=fopen("semne.out", "w");
    for(i=0; i<n; i++){
      if(sol[i]==0)
        sol[i]='-';
      fputc(sol[i], fout);
    }
    fclose(fout);
    return 0;
}