110 Granita

[•SpiderMan]

Mie-mi da 0 la amandoua.

[•Smaug-]

Multumesc am rezolvat-o deja, intelesesem gresit problema, crezand ca daca un aparat este acoperit de doua aparate atunci el este redundant, dar era ca un aparat este redundant doar daca este acoperit in intregime de un singur alt aparat.

[•ctlin04]

in sfirsit am rezolvat si eu problema pe 100, cind foloseam bublesort obtineam 80 dar totusi insertia este mai rapida si mai eficienta, cu toate ca testul 3 nu stiu din care motive a mers la limita celelalte teste sunt destul de rapide. Pentru cei care inca nu au rezolvat problema recomand insertia pentru a lua 100.

[•harababurel]

O intrebare: cum sortez cu functia qsort() un tablou bidimensional, pe baza compararii unei singure coloane?
Mai exact, daca am matricea a[j], vreau ca prima coloana sa fie sortata crescator, iar asupra celei de-a doua sa se efectueze exact aceleasi interschimbari (daca in matricea a initiala, numerele i si j de pe o anumita linie sunt pereche (sunt pe aceeasi linie), si in matricea finala, sa ramana tot pereche (sa ramana pe aceeasi linie)).

[•psycho21r]

Nu interschimbi, iei un vector separat pe care îl sortezi, dar nu comparând elementele din vector, ci comparând elementele din matricea ta.

[•harababurel]

Si asta cum fac?

[•klamathix]

Treci pe STL si e mai simplu.

Cod:

#include<algorithm> // pentru sortare
#include<vector>
#include<iostream>
using namespace std;
int i , n , a , b;
vector< pair<int , int> > v;

int main()
{
for(i = 1; i <= n; ++i) {
cin >> a >> b;
v.push_back(make_pair(a, b));
}

sort(v.begin() , v.end());

return 0;
}

Un element A de tip pair<int , int> este o pereche de doua numere intregi. A.first este primul element, iar A.second este cel de-al doilea. make_pair(a, b) iti returneaza un pair constituit din elementele a si b. Aici ai nevoie de mai multe perechi, deci am declarat un vector <> de pair-uri. Vectorul asta are initial marime 0, iar ca sa adaugi elemente la el folosesti v.push_back(element). In cazul de fata, element este de tip pair.

Sortarea este din biblioteca <algorithm> si sorteaza un vector intre capetele date. Pentru perechi, criteriul de comparare implicit este crescator dupa primul element iar in caz de egalitate dupa al doilea. Daca doresti un alt criteriu, poti da ca al treilea parametru o functie de comparare.

Mai multe detalii gasesti pe
http://cplusplus.com/reference/stl/vector/
http://cplusplus.com/reference/algorithm/sort/

Iti recomand sa inveti STL  Codul poate deveni foarte elegant si scurt daca il folosesti cum trebuie.

[•harababurel]

Multumesc, cu metoda asta am reusit sa iau suta

[•Detrol2k]

Cum poti face verificarea intr-un timp mai mic de N^2 ?

[•SebiSebi]

Poti rezolva mai intai problema http://infoarena.ro/problema/linterv (daca nu stii cum , are solutie oficiala). Succes!

[•Detrol2k]

Poti rezolva mai intai problema http://infoarena.ro/problema/linterv (daca nu stii cum , are solutie oficiala). Succes!

Desteapta sugestia! Am reusit sa le fac pe amandoua de 100! Traiasca familia ta!  

[•freak93]

Pe linux in versiunea noastra de GCC nu acolo se gaseste INT_MAX. E de preferat sa folosesti numeric_limits<int>::max() in loc. (Incluzi limits(fara .h)).

Si Visual Studio nu e tocmai un argument ca merge. El nu prea respecta toate regulile legate de C++. De exemplu tu in clasa definesti operatorul cu paramtrii const(const Boundary &a, const Boundary &b) ... etc,  dar implementezi in exterior fara const. Modifica in ambele locuri sa ai la fel.

L.E:
Vezi ca inline in interiorul unei clase nu face nimic. Orice functie pe care o implementezi dupa class ... { si inainte sa inchizi acolada se defineste inline. Daca o implementezi in exterior(cum faci tu) trebuie sa o dai ca inline acolo unde o implementezi.

L.L.E: @jumper007 De ce iti stergi posturile? Poate lumea invata ceva din intrebarile pe care le pui mai tarziu cand se uita

[•Opportunity]

nush cum la voi la mine cu quicksort a mers pe maxim 12ms 

struct dvc{long a,b;};

void qsort(long l,long r){
    long i=l,j=r,p=t[(l+r)/2].a; dvc aux;
    while (i<j){
        while (t.a<p) i++;
        while (t[j].a>p) j--;
        if (i<=j) aux=t, t=t[j], t[j]=aux, i++, j--;
    }
    if (j>l) qsort(l,j);
    if (i<r) qsort(i,r);
}

[•DavidBogdan]

ce inseamna Killed by signal 11(SIGSEGV)

[•DavidBogdan]

ce inseamna Killed by signal 11(SIGSEGV)

[•Owlree]

SIGSEGV este un semnal pe care, de obicei, sistemele tip unix la trimit proceselor care comit segmentation facult, sau mai exact access violation. Acest lucru întâmplă atunci când încerci să accesezi o zonă de memorie care nu îți este destinată. De exemplu, dacă ai declara un vector de 10 elemente int a[10] și după ai vrea să folosești a[15], ar fi foarte probabil ca programul tău să primească SIGSEGV.

Recomand să citești acest articol din documentația evaluatorului de pe infoarena.