Pagini recente » Cod sursa (job #2494502) | Cod sursa (job #1084882) | Istoria paginii runda/pt_round13 | Cod sursa (job #2348708) | Cod sursa (job #986129)
Cod sursa(job #986129)
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
#define Nmax 50005
long long S;
int N, suma, r;
int v[Nmax];
int pozi[Nmax], nega[Nmax];
int semne[Nmax];
void read()
{
ifstream f("semne.in");
f>>N>>S;
bool r;
srand(time(0));
for(int i = 1;i <= N; ++i)
{
f >> v[i];
r = rand()%2;
semne[i] = r;
if(r)
{
suma += v[i];
pozi[++pozi[0]] = i;
}
else
{
suma -= v[i];
nega[++nega[0]] = i;
}
}
}
void solve()
{
int r;
while(suma!=S)
{
if(suma<S)
{
r = (rand()%nega[0])+1;
suma += 2*v[nega[r]];
semne[nega[r]] = 1;
pozi[++pozi[0]] = nega[r];
nega[r] = nega[nega[0]--];
}
if(suma>S)
{
r = (rand()%pozi[0])+1;
suma -= 2*v[pozi[r]];
semne[pozi[r]] = 0;
nega[++nega[0]] = pozi[r];
pozi[r] = pozi[pozi[0]--];
}
}
}
void print()
{
ofstream g("semne.out");
for ( int i = 1; i <= N; ++i )
{
if ( semne[i] == 1 )
g << "+";
else
g << "-";
}
g << "\n";
g.close();
}
int main()
{
read();
solve();
print();
return 0;
}