Jedno možné riešenie

Pozrime sa na to, čo sa stane, ak kladné čísla dáme do kladného kamiónu, záporné do záporného a nuly do nulového. Keďže vieme, že riešenie existuje, tak v zápornom kamióne bude aspoň jedno číslo, keďže na to, aby súčin bol záporný potrebujeme aspoň jedno záporné číslo. Taktiež v nulovom kamióne bude aspoň jedna nula. V kladnom kamióne teoreticky nemusí byť ani jedno číslo. V prípade, že tam nie je ani jedno, tak môžeme presunúť dve ľubovoľné záporné čísla zo záporného kamióna do kladného. Tým sa nám súčin čísel v zápornom kamióne nezmení, ale kladný kamión už bude obsahovať nejaké čísla (ktorých súčet je kladný), takže náš problém je vyriešený. Ešte môže nastať situácia, že v zápornom kamióne je párny počet záporných čísel. V tom prípade môžeme presunúť jedno záporné číslo do nulového kamiónu, aby súčin v zápornom bol záporný a v nulovom stále ostane nulový. Týmto spôsobom sme vyriešili úlohu.

Ďalšie riešenie

Ďalšie riešenie bolo založené na tom, že do záporného kamiónu dáme prvé záporné číslo. Do kladného kamiónu dáme 1 kladné číslo (alebo 2 záporné ak kladné neexistuje) a do nulového kamiónu zvyšné čísla. Takýto prístup tiež bez problémov vyriešil úlohu.

Zložitosti

V oboch prípadoch je pamäťová zložitosť riešenia $O(n)$, keďže si náš program musí pamätať všetky čísla. Je to preto, lebo čísla musíme ich na konci vypísať a nevieme to urobiť tak, že ich vypisujeme postupne, keďže musíme napísať, koľko ich dokopy v ktorom kamióne bude. Časová zložitosť je tiež $O(n)$, keďže prechádzame čísla po jednom a pre každé z nich urobíme iba konštantné množstvo operácií (jednoducho ho iba zaradíme do niektorej množiny).

N = int(input())
A = list(map(int, input().split()))

neg, zero, pos = [], [], []

for i in range(N):
    if (A[i] < 0):
        neg.append(A[i])
    elif (A[i] == 0):
        zero.append(A[i])
    else:
        pos.append(A[i])

if (len(pos) == 0):
    pos.append(neg[-1])
    neg.pop(-1)
    pos.append(neg[-1])
    neg.pop(-1)

if (len(neg)%2 == 0):
    zero.append(neg[-1])
    neg.pop()

print(len(neg), " ".join(map(str, neg)))
print(len(pos), " ".join(map(str, pos)))
print(len(zero), " ".join(map(str, zero)))

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N;
    cin >> N;
    vector<int> neg;
    vector<int> zero;
    vector<int> pos;

    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        if (a < 0) neg.push_back(a);
        else if (a == 0) zero.push_back(a);
        else pos.push_back(a);
    }

    if (pos.size() == 0)
    {
        pos.push_back(neg[neg.size()-1]);
        neg.pop_back();
        pos.push_back(neg[neg.size()-1]);
        neg.pop_back();
    }

    if (neg.size()%2 == 0)
    {
        zero.push_back(neg[neg.size()-1]);
        neg.pop_back();
    }

    cout << neg.size();
    for (int i = 0; i < neg.size(); i++) cout << " " << neg[i];
    cout << "\n";

    cout << pos.size();
    for (int i = 0; i < pos.size(); i++) cout << " " << pos[i];
    cout << "\n";

    cout << zero.size();
    for (int i = 0; i < zero.size(); i++) cout << " " << zero[i];
    cout << "\n";
}