Pagini recente » Cod sursa (job #606784) | Cod sursa (job #1723963) | Clasament shimulare | Cod sursa (job #1574155) | Cod sursa (job #1679)
Cod sursa(job #1679)
#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <map>
using namespace std;
#define MAX 50006
int a[MAX];
int R, n, s, sum, semne[MAX], saux;
map<int, int> semn_minus, semn_plus;
map<int, int>::iterator it, start, end;
int countt;
void Write();
void ReSeed();
int main()
{
srand ( time(NULL) );
FILE *fin = fopen("semne.in", "r");
fscanf(fin, "%d%d", &n, &s);
for (int i = 1; i <= n; ++i)
fscanf(fin, "%d", &a[i]);
fclose(fin);
ReSeed();
int aux;
while (1)
{
if (sum == s) { Write(); break; }
if (countt >= 100) ReSeed();
else
{
countt++;
saux = sum - s;
if (saux > 0)
{
saux /= 2;
it = semn_plus.find(saux);
if (it == semn_plus.end())
{
it = semn_plus.upper_bound(saux);
if ((*it).second <= 0)
{
while (it != semn_plus.end() && (*it).second <= 0)
it++;
if (it == semn_plus.end())
while ((*it).second <= 0)
it--;
}
}
aux = (*it).first;
sum -= 2*aux;
semn_plus[aux]--;
// aux2 = (*it).second;
semn_minus[aux]++;
}
else
{
if (saux < 0)
{
saux *= -1;
saux /= 2;
it = semn_minus.find(saux);
if (it == semn_minus.end())
{
it = semn_minus.upper_bound(saux);
if ((*it).second <= 0)
{
while (it != semn_minus.end() && (*it).second <= 0)
it++;
if (it == semn_plus.end())
while ((*it).second <= 0)
it--;
}
}
aux = (*it).first;
sum += 2*aux;
semn_minus[aux]--;
// aux2 = (*it).second;
semn_plus[aux]++;
}
}
}
}
return 0;
}
void Write()
{
FILE *fout = fopen("semne.out", "w");
for (int i = 1; i <= n; ++i)
{
if (semn_minus[a[i]] > 0)
{
fprintf(fout, "-");
semn_minus[a[i]]--;
}
else
{
if (semn_plus[a[i]] > 0)
{
fprintf(fout, "+");
semn_plus[a[i]]--;
}
}
}
fclose(fout);
}
void ReSeed()
{
semn_minus.clear();
semn_plus.clear();
sum = 0;
countt = 0;
for (int i = 1; i <= n; ++i)
{
R = rand()%2;
if (R == 0)
{
if (semn_minus.count(a[i]) == 0)
semn_minus[a[i]] = 1;
else
semn_minus[a[i]]++;
semne[i] = -1;
}
if (R == 1)
{
if (semn_plus.count(a[i]) == 0)
semn_plus[a[i]] = 1;
else
semn_plus[a[i]]++;
semne[i] = 1;
}
sum += a[i] * semne[i];
}
}