Pagini recente » Cod sursa (job #2074741) | Cod sursa (job #1489345) | Istoria paginii utilizator/matei_ioan_mihnea_323ca | Statistici Raluca Lupu (lukaisthewolf) | Cod sursa (job #984798)
Cod sursa(job #984798)
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <bitset>
#define In "semne.in"
#define Out "semne.out"
#define Nmax 50005
using namespace std;
int N, v[Nmax],s0[Nmax],s1[Nmax];
bitset<Nmax>sol;
long long S,sum;
inline void Read()
{
ifstream f(In);
f>>N>>S;
bool r;
srand(time(0));
for(int i = 1;i <= N; ++i)
{
f>>v[i];
r = rand()%2;
sol[i] = r;
if(r)
{
sum += v[i];
s1[++s1[0]] = i;
}
else
{
sum -= v[i];
s0[++s0[0]] = i;
}
}
}
inline void Solve()
{
int r;
while(sum!=S)
{
if(sum<S)
{
r = (rand()%s0[0])+1;
sum += 2*v[s0[r]];
sol[s0[r]] = 1;
s1[++s1[0]] = s0[r];
s0[r] = s0[s0[0]--];
}
if(sum>S)
{
r = (rand()%s1[0])+1;
sum -= 2*v[s1[r]];
sol[s1[r]] = 0;
s0[++s0[0]] = s1[r];
s1[r] = s1[s1[0]--];
}
}
}
inline void Write()
{
ofstream g(Out);
for(int i = 1;i <= N; ++i)
g<<(sol[i]?"+":"-");
g<<"\n";
g.close();
}
int main()
{
Read();
Solve();
Write();
return 0;
}