Ładny brzuch
TRESC ZADANIA
Kod made by ja:
#include<iostream> #include<cstdio> #include<vector> #include<list> #include<algorithm> #include<map> using namespace std; int N, a, b; map<int, int> produkty; vector<int> temp; vector<int> temp2; main() { scanf("%d", &N); while(N--) { scanf("%d %d", &a, &b); if(!binary_search(temp.begin(), temp.end(), a)) { temp.push_back(a); temp2.push_back(a); sort(temp.begin(), temp.end()); } produkty[a] += b; } printf("%d\n", produkty.size()); for(vector<int>::iterator it = temp2.begin(); it != temp2.end(); it++) { printf("%d %d\n", *it, produkty[*it]); } return 0; }
Niestety jest on za wolny (40/100 w mainie...)... Gdyby nie bylo wymogu wypisania wg kolejnosci pojawiania sie to bym sie mogl pozbyc wektorow i na pewno cos by bylo szybciej... a tak to nie wiem jak to przyspieszyc.
A tak swoja droga to moglby mi ktos powiedziec czym dokladnie jest ta struktura danych "mapa"? xD Bo ja z niej korzystam "bo jest fajna, bo moze miec np. indeks 100, a nie musi 1... w dodatku moze miec np. indeksy literowe" a nie mam pojecia czym wogole jest, a w necie za bardzo o tym (po polsku) nie pisza...
Uytkownik Kamil Wajda edytowa ten post 26 marzec 2008, 19:56
Ty nie chcesz tego zoptymalizowa, ty po prostu chcesz zrobi to zadanie, bo na razie masz bruta :D
Nie pamitam rozwizania, ale ley na www.oi.edu.pl w dziale OIGu (s treci zada z rozwizaniami).
[przechwalka mode on]
(40/100 w mainie...)... ja wtedy na zawodach wycignem 50 :D
[przechwalka mode off]
A mapa jest AFAIK zrealizowana jako drzewo czerwono-czarne (czyli takie "fajniejsze BST"), ktrego elementami s pary klucz+warto.
@down:
dostp do okrelonego elementu jest w czasie O(n) . vs
Complexity
Logarithmic in size. ?
Uytkownik bryn edytowa ten post 26 marzec 2008, 20:59
Mapa to inaczej hashtablica, tablica asocjacyjna, sownik, czy jeszcze inaczej jest winnych jzykach. Struktura jest taka, e przypisuje si pewnemu cigowi danych inny cig danych. Tym pierwszym cigiem jest zwykle tzw. hash, dla rnych danych jest zwykle rny. W zwizku z tym dostp do okrelonego elementu jest w czasie O(n) .
Niestety jest on za wolny (40/100 w mainie...)... Gdyby nie bylo wymogu wypisania wg kolejnosci pojawiania sie to bym sie mogl pozbyc wektorow i na pewno cos by bylo szybciej... a tak to nie wiem jak to przyspieszyc.
A tak swoja droga to moglby mi ktos powiedziec czym dokladnie jest ta struktura danych "mapa"? xD Bo ja z niej korzystam "bo jest fajna, bo moze miec np. indeks 100, a nie musi 1... w dodatku moze miec np. indeksy literowe" a nie mam pojecia czym wogole jest, a w necie za bardzo o tym (po polsku) nie pisza...
Pisz, tylko nie pod t nazw. Polecam tak kolejno lektury: BST, AVL, drzewo czerwono-czarne. Jest chyba tak jak bryn napisa, czyli mapa w STL jest implementowana jako drzewo czerwono-czarne.
Zamiast wektora, ktry za kadym razem musisz sortowa (i tu jest wskie gardo), moesz uywa set'a, ktry sam szybko sortuje i dba o unikalno.
set<int> numery; ... scanf("%d %d", &a, &b); numery.insert(a); produkty[a] += b; ...
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
Kod made by ja:
#include<iostream> #include<cstdio> #include<vector> #include<list> #include<algorithm> #include<map> using namespace std; int N, a, b; map<int, int> produkty; vector<int> temp; vector<int> temp2; main() { scanf("%d", &N); while(N--) { scanf("%d %d", &a, &b); if(!binary_search(temp.begin(), temp.end(), a)) { temp.push_back(a); temp2.push_back(a); sort(temp.begin(), temp.end()); } produkty[a] += b; } printf("%d\n", produkty.size()); for(vector<int>::iterator it = temp2.begin(); it != temp2.end(); it++) { printf("%d %d\n", *it, produkty[*it]); } return 0; }
Niestety jest on za wolny (40/100 w mainie...)... Gdyby nie bylo wymogu wypisania wg kolejnosci pojawiania sie to bym sie mogl pozbyc wektorow i na pewno cos by bylo szybciej... a tak to nie wiem jak to przyspieszyc.
A tak swoja droga to moglby mi ktos powiedziec czym dokladnie jest ta struktura danych "mapa"? xD Bo ja z niej korzystam "bo jest fajna, bo moze miec np. indeks 100, a nie musi 1... w dodatku moze miec np. indeksy literowe" a nie mam pojecia czym wogole jest, a w necie za bardzo o tym (po polsku) nie pisza...
Uytkownik Kamil Wajda edytowa ten post 26 marzec 2008, 19:56
Ty nie chcesz tego zoptymalizowa, ty po prostu chcesz zrobi to zadanie, bo na razie masz bruta :D
Nie pamitam rozwizania, ale ley na www.oi.edu.pl w dziale OIGu (s treci zada z rozwizaniami).
[przechwalka mode on]
(40/100 w mainie...)... ja wtedy na zawodach wycignem 50 :D
[przechwalka mode off]
A mapa jest AFAIK zrealizowana jako drzewo czerwono-czarne (czyli takie "fajniejsze BST"), ktrego elementami s pary klucz+warto.
@down:
dostp do okrelonego elementu jest w czasie O(n) . vs
Complexity
Logarithmic in size. ?
Uytkownik bryn edytowa ten post 26 marzec 2008, 20:59
Mapa to inaczej hashtablica, tablica asocjacyjna, sownik, czy jeszcze inaczej jest winnych jzykach. Struktura jest taka, e przypisuje si pewnemu cigowi danych inny cig danych. Tym pierwszym cigiem jest zwykle tzw. hash, dla rnych danych jest zwykle rny. W zwizku z tym dostp do okrelonego elementu jest w czasie O(n) .
Niestety jest on za wolny (40/100 w mainie...)... Gdyby nie bylo wymogu wypisania wg kolejnosci pojawiania sie to bym sie mogl pozbyc wektorow i na pewno cos by bylo szybciej... a tak to nie wiem jak to przyspieszyc.
A tak swoja droga to moglby mi ktos powiedziec czym dokladnie jest ta struktura danych "mapa"? xD Bo ja z niej korzystam "bo jest fajna, bo moze miec np. indeks 100, a nie musi 1... w dodatku moze miec np. indeksy literowe" a nie mam pojecia czym wogole jest, a w necie za bardzo o tym (po polsku) nie pisza...
Pisz, tylko nie pod t nazw. Polecam tak kolejno lektury: BST, AVL, drzewo czerwono-czarne. Jest chyba tak jak bryn napisa, czyli mapa w STL jest implementowana jako drzewo czerwono-czarne.
Zamiast wektora, ktry za kadym razem musisz sortowa (i tu jest wskie gardo), moesz uywa set'a, ktry sam szybko sortuje i dba o unikalno.
set<int> numery; ... scanf("%d %d", &a, &b); numery.insert(a); produkty[a] += b; ...