Cod sursa(job #2196934)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 20 aprilie 2018 18:06:16
Problema Semne Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <random>
#include <ctime>
#define MAX 50010

using namespace std;
typedef long long ll;

ll n,s,nrp,nr,st,dr,mij,sf;
ll a[MAX];
bool sm[MAX];
ll aib[MAX];
ll nsb(ll nr){return nr^(nr&(nr-1));}
void update(ll nr,ll incr){for(;nr<MAX;nr+=nsb(nr))aib[nr]+=incr;}
ll query(ll nr){
  ll 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(ll i=1;i<=n;i++){
      f>>a[i];
      s+=a[i],sm[i]=1,nrp++,update(i,1);
//      if(s<=sf){
//        s+=a[i],sm[i]=1,nrp++;
//        update(i,1);
//      } else s-=a[i];
    }
    nrp=n; srand(time(0));
    while(s!=sf){
      nr=rand();
      if(s<sf){
        nr=nr%(n-nrp)+1;
        st=0,dr=n-1;
        while(st<dr){
          mij=(st+dr+1)/2;
          if(mij-query(mij)<nr)st=mij;
          else dr=mij-1;
        }
        st++;
        s=s+2*a[st];sm[st]=1;nrp++;
        update(st,1);
      } else {
        nr=nr%nrp+1;
        st=0,dr=n-1;
        while(st<dr){
          mij=(st+dr+1)/2;
          if(query(mij)<nr)st=mij;
          else dr=mij-1;
        }
        st++;
        s=s-2*a[st];sm[st]=0;nrp--;
        update(st,-1);
      }
    }
    for(ll i=1;i<=n;i++)
      if(sm[i]==0)g<<'-';
      else g<<'+';
    g<<'\n';
    f.close ();
    g.close ();
    return 0;
}