Cod sursa(job #986136)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 17 august 2013 19:36:52
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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 pozi[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];

        if ( suma < S )
        {
            suma += a[i];
            pozi[ ++pozi[0] ] = i;
            semne[i] = 1;
        }
        else
        {
            suma -= a[i];
            nega[ ++nega[0] ] = i;
            semne[i] = 0;
        }
    }

    f.close();
}

void solve()
{
    while( suma != S)
    {
       if(suma > S)
       {
           ind=rand()%pozi[0]+1;
           suma-=2*a[pozi[ind]];
           semne[pozi[ind]]=0;
           nega[++nega[0]]=pozi[ind];
           swap(pozi[ind],pozi[pozi[0]]);
           pozi[0]--;
      }
      else
      {
          ind=rand()%nega[0]+1;
          suma+=2*a[nega[ind]];
          semne[nega[ind]]=1;
          pozi[++pozi[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;
}