Użyj vector i map. Oto gotowiec, przepraszam, że zepsułem przyjemność rozwiązywania zadania <haha>:
#include <map>
#include <cstdio>
#include <vector>
int main(int argc, char** argv) {
int _, iloscWierszy;
_ = scanf("%d", &iloscWierszy);
std::map<int, int> ilosci;
std::vector<int> produkty;
for (int wiersz = 0; wiersz < iloscWierszy; wiersz++) {
int produkt, ilosc;
_ = scanf("%d %d", &produkt, &ilosc);
if (ilosci.count(produkt) > 0) {
ilosci[produkt] += ilosc;
} else {
produkty.push_back(produkt);
ilosci[produkt] = ilosc;
}
}
printf("%zu\n", produkty.size());
for (std::vector<int>::const_iterator produkt = produkty.begin(); produkt != produkty.end(); ++produkt) {
printf("%d %d\n", *produkt, ilosci[*produkt]);
}
}
Edit:
Niestety ten program nie mieści się w limicie. Jest ok 13 s, a limit wynosi 10 s. Generalnie sprawę załatwiłoby zamienienie mapy na hash_mapę, ale nie wiem na razie jak to zapisać. Niby nagłówek <hash_map> jest, ale jak tego użyć? :P
Zrobiłem własną hash mapę:
#include <cstdio>
#include <cstring>
struct Produkt {
int numer;
int ilosc;
};
const int MaxProduktow = 1024 * 1024;
Produkt mapa[MaxProduktow];
Produkt* produkty[MaxProduktow];
int main(int argc, char** argv) {
int _, iloscWierszy;
_ = scanf("%d", &iloscWierszy);
int produktow = 0;
memset(mapa, -1, sizeof (mapa));
for (int wiersz = 0; wiersz < iloscWierszy; wiersz++) {
int numer, ilosc;
_ = scanf("%d %d", &numer, &ilosc);
int hash = (numer * 23452457) & (MaxProduktow - 1);
while ((mapa[hash].numer != numer) && (mapa[hash].numer != -1)) {
hash = (hash + 7) & (MaxProduktow - 1);
}
if (mapa[hash].numer == -1) {
mapa[hash].numer = numer;
mapa[hash].ilosc = ilosc;
produkty[produktow] = &mapa[hash];
produktow++;
} else {
mapa[hash].ilosc += ilosc;
}
}
printf("%d\n", produktow);
for (int produkt = 0; produkt < produktow; produkt++) {
printf("%d %d\n", produkty[produkt]->numer, produkty[produkt]->ilosc);
}
}
Teraz czas jest lepszy.
Edit:
Tak jak sądziłem, samodzielne parsowanie może przyspieszyć znacznie program. Z tym programem wylądowałem na 5 miejscu w zestawieniu najlepszych:
#include <cstdio>
#include <cstring>
struct Produkt {
int numer;
int ilosc;
};
const int MaxProduktow = 1024 * 1024;
Produkt mapa[MaxProduktow];
Produkt* produkty[MaxProduktow];
char buforWejscia[15 * 1000 * 1000 + 20];
int main(int argc, char** argv) {
int _, iloscWierszy;
_ = scanf("%d", &iloscWierszy);
int produktow = 0;
memset(mapa, -1, sizeof (mapa));
int wczytanychBajtow = fread(buforWejscia, 1, sizeof (buforWejscia) - 1, stdin);
buforWejscia[wczytanychBajtow] = 0;
int bajt = 0;
for (int wiersz = 0; wiersz < iloscWierszy; wiersz++) {
bajt += 1;
int numer = 0;
while (buforWejscia[bajt] >= '0') {
numer *= 10;
numer += buforWejscia[bajt] - '0';
bajt++;
}
bajt += 1;
int ilosc = 0;
while (buforWejscia[bajt] >= '0') {
ilosc *= 10;
ilosc += buforWejscia[bajt] - '0';
bajt++;
}
int hash = ((((((2166136261 * 16777619) ^ (numer & 0xff)) * 16777619) ^ ((numer >> 8) & 0xff)) * 16777619) ^
(numer >> 16)) & (MaxProduktow - 1);
while ((mapa[hash].numer ^ numer) > 0) {
hash = (hash + 1) & (MaxProduktow - 1);
}
if (mapa[hash].numer == -1) {
mapa[hash].numer = numer;
mapa[hash].ilosc = ilosc;
produkty[produktow] = &mapa[hash];
produktow++;
} else {
mapa[hash].ilosc += ilosc;
}
}
printf("%d\n", produktow);
for (int produkt = 0; produkt < produktow; produkt++) {
printf("%d %d\n", produkty[produkt]->numer, produkty[produkt]->ilosc);
}
}
Pewnie sporo da się jeszcze przyspieszyć wczytywanie, bo najlepsi mają kilkadziesiąt procent szybsze programy.