Cod sursa(job #986135)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 17 august 2013 19:35:02
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>

using namespace std;

#define Nmax 50005

long long N, S, suma, ind;
int a[Nmax];
int indi[Nmax], nega[Nmax];
int semne[Nmax];

void read()
{
    ifstream f("semne.in");

    f >> N >> S;

    srand( time( NULL ) );

    for ( int i = 1; i <= N; ++i )
    {
        f >> a[i];

        suma += a[i] * 1LL;
        indi[ ++indi[0] ] = i;
        semne[i] = 1;
    }

    f.close();
}

void solve()
{
    while( suma != S)
    {
       if(suma > S)
       {
           ind=rand()%indi[0]+1;
           suma-=2*a[indi[ind]];
           semne[indi[ind]]=0;
           nega[++nega[0]]=indi[ind];
           swap(indi[ind],indi[indi[0]]);
           indi[0]--;
      }
      else
      {
          ind=rand()%nega[0]+1;
          suma+=2*a[nega[ind]];
          semne[nega[ind]]=1;
          indi[++indi[0]]=nega[ind];
          swap(nega[ind],nega[nega[0]]);
          nega[0]--;
      }
    }
}

void print()
{
    ofstream g("semne.out");

    for ( int i = 1; i <= N; ++i )
    {
        if ( semne[i] == 1 )
                g << "+";
        else
                g << "-";
    }

    g << "\n";

    g.close();
}

int main()
{
    read();
    solve();
    print();

    return 0;
}