Jak przyspieszyć mój algorytm?

Cześć,
Rozwiązuję to zadanie:
https://szkopul.edu.pl/problemset/problem/plwJuavOqAD9XxBqllCwJRK3/site/?key=statement
Kompletnie nie mam pojęcia co mogę zrobić z moim rozwiązaniem, które dostaje 80% pkt, aby było szybsze i przeszło wszystkie testy. Wygląda ono tak:
https://4programmers.net/Pastebin/14743
Jaka jest złożoność mojego algorytmu? Nie potrafię tego ocenić.
Proszę o wskazówki.

Z podstawowych rzeczy:

1. Używaj statycznych tablic w takich zadaniach, nie przejmuj się z reguły pamięcią. Statyczna alokacja jest zdecydowanie szybsza.
2. Jeśli już musisz użyć dynamicznej alokacji (jak std::vector) to użyj reserve jeśli znasz wynikowy rozmiar. Pojedyncza alokacja będzie zdecydowanie szybsza niż to co masz teraz, które co jakiś czas musi realokować tablicę i kopiować wszystkie elementy.

Z pozostałych:

1. Podziel kod na funkcje, to nie lata 80te by to spowalniało kod, a będzie się go zdecydowanie łatwiej czytało.

Co do algorytmu, to nie wgłębiałem się mocno, ale zapewne zastosowanie będą tutaj miały liczby trójkątne.

Da się zrobić z kosztem pamięciowym O(1)

#include <iostream>
using namespace std;

int main()
{
   int n,s;
   cin>>n>>s;
   int minmax=(n*n-n)>>1;
   if((-minmax>s)||(s>minmax)||((minmax^s)&1)) cout<<"NIE"<<endl;
   else
   {
      cout<<0<<endl;
      for(int delta=(minmax-s)>>1,v=0;--n;cout<<v<<endl)
      {
         int dec=(delta>=n);
         if(dec) delta-=n;
         v+=1-(dec<<1);
      }
   }
   return 0;
}

https://ideone.com/gJoyhR
Tylko mam jedno pytanie do tego zadania ...
W sumie rozwiązań może być wiele, na przykład dla 8 4 rozwiązań jest tyle na ile sposobów można dostać liczbę:
14 jako sumę elementów 1,2,3,4,5,6,7,8, np 8+6 lub 6+4+3+1 lub 5+4+3+2
Więc w sumie zadanie niewystarczająco sprecyzowane.

@hauleth: Dzięki za rady.
@_13th_Dragon: W zadaniach OI zawsze jest tak, że jeśli istnieje wiele odpowiedzi do zadania to można wypisać dowolną (przynajmniej nigdy się nie spotkałem z odmiennym przypadkiem). Mógłbym Cię prosić o opisanie pokrótce tego algorytmu? Nie rozumiem jak on działa.

Maksymalna liczba kiedy cały czas idziemy w górę i jest to suma ciągu arytmetycznego: (n*n-n)/2 -> minmax
Zauważ że:

• jak zmienimy ostatnią liczbę na idącą w dół zamiast w górę to suma nam spadnie o 2
• jak zmienimy przedostatnią liczbę na idącą w dół zamiast w górę (oczywiście dalej też będzie wszystko pozmieniać) suma nam spadnie o 4
• jak zmienimy k-tą od końca to suma nam spadnie o k*2
  Natomiast sumę musimy zmniejszyć o: (n*n-n)/2-s ja to dziele przez 2 -> delta aby zmniejszać o k a nie o 2*k
  To int dec=(delta>=n); decyduje czy idziemy w dół.