Cod sursa(job #1248202)

Utilizator DjokValeriu Motroi Djok Data 24 octombrie 2014 19:26:35
Problema Semne Scor 95
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.93 kb
#include<fstream>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;

typedef struct lol {
        int x,poz;
}troll;

int a[50005],i,n,aux,q,nr;
long long s,sum;
bool rs[50005];
troll m[50005],p[50005];

int main()
{
  ifstream cin("semne.in");
  ofstream cout("semne.out");

  srand(time(NULL));

  cin>>n>>s;
  for(i=1;i<=n;++i)
  {
    cin>>a[i]; aux=rand()%2;
    if(aux) sum+=a[i],p[++nr].x=a[i],p[nr].poz=i;
    else sum-=a[i],m[++q].x=a[i],m[q].poz=i;
  }

  while(sum!=s)
  if(sum<s) {
              aux=rand()%q;
              p[++nr]=m[aux+1];
              sum+=2*m[aux+1].x;
              swap(m[aux+1],m[q--]);
            }
  else {
         aux=rand()%nr;
         m[++q]=p[aux+1];
         sum-=2*p[aux+1].x;
         swap(p[aux+1],p[nr--]);
       }

  for(i=1;i<=q;++i) rs[m[i].poz]=1;

  for(i=1;i<=n;++i)
  if(rs[i]) cout<<'-'; else cout<<'+';

 return 0;
}