Zadanie "Czwórki" - złe odpowiedzi

Question

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;
}

 

Answer 1

1) Liczby są parami różne więc niepotrzebnie wywalasz duplikaty

2) Pojedyncza liczba może mieć pół miliona więc ich suma może być do miliona

if (sum <= 500000) /// zamień na milion

3) Nie wiem po co robisz to głupie -1 w liczniku. Tylko się pomylić można

4) Poza tym wygląda to w porządku, no jeszcze mógłbyś wektora na tablice zamienić

Comments

Dzięki za pomoc. Okazało się, że program podawał zły wynik, gdy w ciągu podanym na wejściu znajdowało się 0. Zmieniłem więc rozmiar tablicy present na 500001 i obecność danej pary zaznaczałem w present[sum], a nie w present[sum-1].