Pagini recente » Cod sursa (job #2599110) | Cod sursa (job #353649) | Cod sursa (job #142847) | Cod sursa (job #1636207) | Cod sursa (job #2196934)
#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;
}