Cod sursa(job #986137)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 17 august 2013 19:39:04
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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] = -1;
        }
    }

    f.close();
}

void solve()
{
    srand( time( NULL ) );

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