Cześć,
niedawno postanowiłem rozwiązać zadanie "Czwórki" (http://ki.staszic.waw.pl/task.php?name=czworki), w którym trzeba wyznaczyć wszystkie czwórki elementów x, y, z, w, należących do zbioru podanego na wejściu, dla których x+y+z = w. Wpadłem na taki pomysł, aby przekształcić ten wzór na x+y=w-z, a następnie wyznaczyć wszystkie pary x+y i ilość wystąpień każdej pary odnotować w tablicy present pod indeksem x+y-1. Następnie obliczam wszystkie pary w-z i jeżeli w present[w-z-1] znajduje się wartość większa od 0 to dodaję tą wartość do wyniku. Zaimplementowałem to rozwiązanie i wysłałem na sprawdzarkę, ale dostaję tylko 70% punktów, a w pozostałych 30% przypadkach mój program podaje złą odpowiedź. Męczę się z tym zadaniem już drugi dzień i nie mam pomysłu, co mój program robi źle. Bardzo prosiłbym o pomoc w znalezieniu źródła problemu.
Oto moja implementacja:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long int l;
typedef long long int ll;
typedef bool b;
typedef vector<l> vl;
#define FOR(x, y, z) for(l z = x; z < y; z++)
#define FORDE(x, y, z) for(l z = x; z >= y; --z)
#define REP(x, y) for(l y = 0; y < x; ++y)
#define PB push_back
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
ll num_of_numbers, result = 0, sum = 0;
cin >> num_of_numbers;
vl numbers;
ll* present = new ll[500 * 1000];
REP(500000, i)
present[i] = 0;
REP(num_of_numbers, i)
{
l a;
cin >> a;
numbers.PB(a);
}
sort(numbers.begin(), numbers.end());
numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());
num_of_numbers = numbers.size();
FOR(0, num_of_numbers, i)
{
sum = numbers[i];
FOR(0, num_of_numbers, j)
{
sum += numbers[j];
if (sum <= 500000)
present[sum - 1]++;
sum -= numbers[j];
}
}
FORDE(num_of_numbers - 1, 0, i)
{
sum = numbers[i];
FORDE(i, 0, j)
{
sum -= numbers[j];
if (sum > 0 && present[sum - 1] > 0)
result += present[sum - 1];
sum += numbers[j];
}
}
cout << result;
}