Cod sursa(job #2196616)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 19 aprilie 2018 20:54:31
Problema Semne Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <random>
#define MAX 50010

using namespace std;

int n,s,nrp,nr,st,dr,mij,sf;
int a[MAX];
bool sm[MAX];
int aib[MAX];
int nsb(int nr){return nr^(nr&(nr-1));}
void update(int nr,int incr){for(;nr<MAX;nr+=nsb(nr))aib[nr]+=incr;}
int query(int nr){
  int ansa=0;
  for(;nr;nr-=nsb(nr))ansa+=aib[nr];
  return ansa;
}

int main()
{
    ifstream f ("semne.in");
    ofstream g ("semne.out");
    f>>n>>sf; for(int i=1;i<=n;i++)f>>a[i],s+=a[i],sm[i]=1,update(i,1);
    nrp=n;
    default_random_engine g1,g2;
    uniform_int_distribution<int> distribution(1,n);  //??
    while(s!=sf){
      //cout<<nr<<'\n';
      if(s<sf){
        nr=distribution(g1);
//        cout<<"\ns<sf\n";
//        for(int i=1;i<=n;i++)cout<<((sm[i])?"+ ":"- ");
//        cout<<'\n'<<nr<<" \n";
        if(sm[nr]==0)s+=2*a[nr];
        sm[nr]=1;
      } else {
        nr=distribution(g2);
//        cout<<"\ns>sf\n";
//        for(int i=1;i<=n;i++)cout<<((sm[i])?"+ ":"- ");
//        cout<<'\n'<<nr<<" \n";
        if(sm[nr]==1)s-=2*a[nr];
        sm[nr]=0;
      }
    }
    for(int i=1;i<=n;i++)
      if(sm[i]==0)g<<'-';
      else g<<'+';
    g<<'\n';
    f.close ();
    g.close ();
    return 0;
}