Pagini recente » Cod sursa (job #2920528) | Cod sursa (job #2587931) | Cod sursa (job #1947893) | Cod sursa (job #957645) | Cod sursa (job #1471533)
/*http://www.infoarena.ro/problema/semne*/
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#define N 50002
using namespace std;
struct nums
{
int x, poz;
} sub[N], add[N];
int v[N], i, n, poz, p, m;
long long s, sum;
bool semn[N];
int main()
{
ifstream f("semne.in");
ofstream g("semne.out");
srand(time(NULL));
f >> n >> s;
for(i=1; i<=n; ++i)
{
f >> v[i];
poz = rand() % 2;
if(poz)
{
sum += v[i];
add[++p].x = v[i];
add[p].poz = i;
}
else
{
sum -= v[i];
sub[++m].x = v[i];
sub[m].poz = i;
}
}
while(sum != s)
{
if(sum < s)
{
poz = 1 + rand() % m;
add[++p] = sub[poz];
sum += 2*sub[poz].x;
swap(sub[poz], sub[m--]);
}
else
{
poz = 1 + rand() % p;
sub[++m] = add[poz];
sum -= 2*add[poz].x;
swap(add[poz], add[p--]);
}
}
for(i=1; i<=m; ++i)
semn[sub[i].poz] = 1;
for(i=1; i<=n; ++i)
if(semn[i]) g << "-";
else g << "+";
f.close();
g.close();
return 0;
}