Pagini recente » Monitorul de evaluare | Cod sursa (job #1714141) | Cod sursa (job #506468) | Cod sursa (job #1290783) | Cod sursa (job #773140)
Cod sursa(job #773140)
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
int m1[50005];
int m2[50005];
int x[50005];
int main () {
ifstream fin ("semne.in");
int N, a, j = -1, k = -1;
long long S, Sp = 0, Slol = 0;
int v[50005];
fin >> N >> S;
for (int i = 0; i < N; i++)
{
fin >> v[i];
Sp += 1LL * v[i];
}
Sp = (Sp - S) >> 1;
srand (time (0));
for (int i = 0; i < (N >> 1); i++)
m1[++j] = i, Slol += v[i];
for (int i = (N >> 1); i < N; i++)
m2[++k] = i;
while (Slol != Sp)
{
if (Slol < Sp)
{
a = rand () % (k + 1);
Slol += v[m2[a]];
m1[++j] = m2[a];
m2[a] = m2[k--];
}
if (Slol > Sp)
{
a = rand () % (j + 1);
Slol -= v[m1[a]];
m2[++k] = m1[a];
m1[a] = m1[j--];
}
}
for (int i = 0; i <= j; i++)
{
x[m1[i]] = 1;
}
ofstream fout ("semne.out");
for (int i = 0; i < N; i++)
{
fout << (x[i] == 1 ? '-' : '+');
}
fin.close ();
fout.close ();
return 0;
}