Cod sursa(job #2765427)

Utilizator euyoTukanul euyo Data 26 iulie 2021 20:06:09
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

ifstream fin( "semne.in" );
ofstream fout( "semne.out" );

const int MAXN = 50002;

vector<int> _add, _dec;

int v[MAXN];
int sign[MAXN];

void del( vector<int> &v, int pos ) {
  swap( v[v.size() - 1], v[pos] );
  v.pop_back();
}

int main() {
  int n, ind;
  long long cs = 0, s;

  fin >> n >> s;
  srand( time( NULL ) );
  for ( int i = 0; i < n; ++i ) {
	fin >> v[i];
    _add.push_back( i );
	cs += v[i]; 
  }  
  while ( cs != s ) {
	if ( cs < s ) {
	  ind = rand() % _dec.size();
      cs += v[_dec[ind]] * 2;
	  _add.push_back( _dec[ind] );
	  del( _dec, ind );
	} else {
	  ind = rand() % _add.size();
      cs -= v[_add[ind]] * 2;
	  _dec.push_back( _add[ind] );
	  del( _add, ind );
	}
  }
  for ( int i = 0; i < _add.size(); ++i ) {
    sign[_add[i]] = 1;
  }
  for ( int i = 0; i < n; ++i ) {
	fout << (sign[i] == 1 ? '+' : '-');
  }
  fin.close();
  fout.close();
  return 0;
}