Pagini recente » Cod sursa (job #1787972) | Cod sursa (job #1729535)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream in("semne.in");
ofstream out("semne.out");
const int maxn = 50005;
int sir1[maxn];
int sir2[maxn];
int v[maxn];
int n, lg1, lg2;
long long sum, s;
void _move_(bool ok)
{
if(ok == 1)
{
int poz = rand() % lg1 + 1;
swap(sir1[poz], sir1[lg1]);
sir2[++lg2] = sir1[lg1];
sum = sum - 2 * v[sir1[lg1]];
lg1--;
}
else
{
int poz = rand() % lg2 + 1;
swap(sir2[poz], sir2[lg2]);
sir1[++lg1] = sir2[lg2];
sum = sum + 2 * v[sir2[lg2]];
lg2--;
}
}
int main()
{
in >> n >> s;
srand(time(0));
for(int i = 1; i <= n; i++)
{
in >> v[i];
if(sum < s)
{
sir1[++lg1] = i;
sum += v[i];
}
else
{
sir2[++lg2] = i;
sum -= v[i];
}
}
while(sum != s)
{
if(sum < s)
_move_(0);
else
_move_(1);
}
sort(sir1 + 1, sir1 + lg1 + 1);
sort(sir2 + 1, sir2 + lg2 + 1);
int poz1 = 1;
int poz2 = 1;
while(poz1 <= lg1 && poz2 <= lg2)
{
if(v[sir1[poz1]] < v[sir2[poz2]])
{
out << '+';
poz1++;
}
else
{
out << '-';
poz2++;
}
}
while(poz1 <= lg1)
{
poz1++;
out << '+';
}
while(poz2 <= lg2)
{
poz2++;
out << '-';
}
out << "\n";
return 0;
}