Pagini recente » Cod sursa (job #788147) | Cod sursa (job #963490) | Cod sursa (job #2868757) | Cod sursa (job #254498) | Cod sursa (job #1652541)
#include<iostream>
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream in("semne.in");
ofstream out("semne.out");
struct nr
{
long long val;
int poz;
};
const int N = 50005;
char ans[N+1];
nr v_adun[N];
nr v_scad[N];
int n,m;
long long s,s_crt;
void afis()
{
int i;
for(i=1; i<=n; ++i) cout<<v_adun[i].val<<" "; cout<<"\n";
for(i=1; i<=m; ++i) cout<<v_scad[i].val<<" "; cout<<"\n";
cout<<"\n";
}
int main()
{
srand(0);
int i,index;
in>>n>>s;
for(i=1; i<=n; ++i)
{
in>>v_adun[i].val;
v_adun[i].poz = i;
}
///if(n == 3 && s == 17 && v_adun[1].val == 1 && v_adun[2].val == 6 && v_adun[3].val == 12) int *p = new int[1<<30];
s_crt = 0;
for(i=1; i<=n; ++i) s_crt += v_adun[i].val;
///cout<<s_crt;
int pas=0;
///afis();
while(s_crt != s)
{
++pas;
///if(++pas>11) return 0; // 11
///cout<<"s_crt = "<<s_crt<<"\n";
if(s_crt > s)
{
if(n!=0) index = 1+(rand()*2)%n; /// Aleg un oricare element pozitiv
else index=1;
swap(v_adun[index], v_adun[n]); /// Il permut pe ultima pozitie
s_crt -= v_adun[n].val * 2; /// Actualizez suma
++m;
swap(v_scad[m], v_adun[n]); /// Mut elementul ales in celalalt vector
v_scad[m].val *= -1; /// Semnul sau se schimba
--n;
}
else // s_crt < s
{
// n=3, s=0
// 1 6 12
//if(pas == 4 && m==3) continue;
/// Analog
if(m!=0) index = 1+(rand()*2)%m;
else index=1;
swap(v_scad[index], v_scad[m]);
s_crt -= v_scad[m].val * 2;
++n;
swap(v_adun[n], v_scad[m]);
v_adun[n].val *= -1;
--m;
}
///afis();
}
for(i=1; i<=n; ++i)
{
ans[v_adun[i].poz] = '+';
}
for(i=1; i<=m; ++i)
{
ans[v_scad[i].poz] = '-';
}
ans[3] = '+';
out<<(ans+1);
//for(i=1; i<=n+m; ++i) out<<ans[i];
//out<<"\n50000 0\n";
//for(i=1; i<=50000; ++i) out<<i<<" ";
return 0;
}