infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Airinei Adrian din Ianuarie 13, 2007, 15:45:45


Titlul: cod c++ gresit (?)
Scris de: Airinei Adrian din Ianuarie 13, 2007, 15:45:45
Cod:
#include <algorithm>
using namespace std;

typedef struct edge { int x, y, c; } edge;

int P;
edge A[200010];

int cmp(edge a, edge b)
{
	return a.c <= b.c;
}

// A are P = 100.000 elemente, A[1], A[2]... A[P]
sort(A+1, A+P+1, cmp);

Spre surprinderea mea, la iesirea din functia sort P este egal cu 0 si A contine si el date eronate. Are cineva vreo idee de ce?

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Stefan-Alexandru Filip din Ianuarie 13, 2007, 16:37:57
Sortarea se face dupa o functie de ordonare stricta intre doua elemente.
De asemeni iti recomand sa nu implementezi o functie separata de comparatie, ci sa supraincarci operatorul '<'. In general e mai comod, daca trebuie apelata de mai multe ori.
Cod:
#include <algorithm>
using namespace std;

typedef struct edge { int x, y, c; } edge;

bool operator<(const edge &a, const edge &b) {
      return a.c < b.c;
}

sort(A+1, A+P+1);

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Adrian Vladu din Ianuarie 13, 2007, 17:43:08
Si STL-ul o mai da pe langa  :-' si am patit si eu chestia asta.
Daca micsorezi P sau daca schimbi struct-ul cu ceva mai mic o sa mearga.

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Andrei Grigorean din Ianuarie 13, 2007, 18:32:29
Si eu am patit sa o ia STL-ul pe aratura chiar ieri la o problema de pe ZJU. Se mai intampla... :(

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Mircea Pasoi din Ianuarie 13, 2007, 22:04:06
Cum s-o ia pe aratura?  :eyebrow: STL-ul merge foarte bine daca e folosit cum trebuie...

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Adrian Vladu din Ianuarie 13, 2007, 23:21:05
Are dreptate Stefan, functia de ordonare trebuie sa fie stricta. Schimba "<=" cu "<" in functia de comparare si o sa mearga :wink:

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Andrei Grigorean din Ianuarie 14, 2007, 10:23:17
Citat din mesajul lui: Mircea Pasoi din Ianuarie 13, 2007, 22:04:06
Cum s-o ia pe aratura?  :eyebrow: STL-ul merge foarte bine daca e folosit cum trebuie...

cod care nu merge :
Cod:
if (A[j-1][start[j-1]].x > i-s[j-1].sz()) break;

cod care merge :
Cod:
aux1 = A[j-1][start[j-1]].x;
aux2 = i-s[j-1].sz();
if (aux1 > aux2) break;

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Stefan-Alexandru Filip din Ianuarie 14, 2007, 12:46:12
Citat
cod care nu merge :
Cod:
if (A[j-1][start[j-1]].x > i-s[j-1].sz()) break;

cod care merge :
Cod:
aux1 = A[j-1][start[j-1]].x;
aux2 = i-s[j-1].sz();
if (aux1 > aux2) break;

Nu am reusit sa recreez bug-ul. Dar de ce nu merge? Ce valori difera? Merge la fel daca scoti define-ul pentru size?
Vrem detalii, stimabile.

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Andrei Grigorean din Ianuarie 14, 2007, 16:23:54
aveti aici portiunile din codul meu care intereseaza:

Cod:
#define x first
#define y second
#define sz size

vector<string> s;
vector< pair<int, int> > A[Lmax];

int start[Nmax];
int aux1, aux2, i, j;

aux1 = A[j-1][start[j-1]].x;
aux2 = i-s[j-1].sz();
if (aux1 > aux2) break;

In cazul in care compar direct, fara sa ma folosesc de variabile auxiliare, primesc runtime error. Si culmea e ca la fel se intampla si la mine pe calculator.

Am luat testele oficiale si imi merge totusi pe 9/10 teste in cazul compararii directe.

Probabil ca exista o explicatie logica pentru ceea ce se intampla, insa pe mine ma depaseste situatia.

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Valentin Stanciu din Ianuarie 14, 2007, 18:04:34
wefgef, ai incercat sa pui paranteze? si sa faci type-casting?
Cod:
if ((int)(A[j-1][start[j-1]].x) > (int)(i-s[j-1].sz())) break;

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Bunau Florin din Ianuarie 14, 2007, 19:02:16
Cod:
s[j-1].sz();

wefgef, greseala pe care o faci este ca folosesti .size() la clasa string
corect ar fi .length() .
[later edit] Sorry my bad, implemntarea la Dev c++ arata ca e acelasi lucru...

[mai later edit] 
Ok credca am solutia
Nu se poate sa fie de la faptul ca ai declarat un vector<...> A[] ? practic ai declarat un pointer la o clasa vector ar putea aparea complicatii avand in vedere ca vectorul e alocat dinamic, iar numarul elementelor din vector cand depasesc capacitatea vectorului, acesta se realoca dublandu-si capcitatea.
Astfel daca depasesti sa zicem un anumit numar de elemente (iar acele elemente nu mai au loc dupa coada vectorului sa fie alocate), se produce o realocare, acesta fiind realocat la o alta zona, unde incape. Schimbandu-si locatia. vectorul vechi se distruge si astfel tu accesezi o zona de memorie unde nu ai voie.
Declara vector<vector<..> >

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Tofan Vasile din Ianuarie 14, 2007, 19:48:05
 :-'...

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Bunau Florin din Ianuarie 14, 2007, 19:59:56
Credca wefgef a vrut sa declare o matrice de pair, nu un sir.
Dupa cum spuneam nu e bine sa fie declarata asa datorita mecanismului de ralocare a vectorului. Corect ar fi vector<vector<pair<int, int > > >

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Valentin Stanciu din Ianuarie 14, 2007, 20:07:15
 :-'

Cod:
vector< pair<int, int> > A[Lmax];

declara Lmax vectori de pair<int, int>.. deci A[0] este un vector<parit<int, int> >, A[1] altul..
A[Lmax].size() o sa iasa in balarii... daca declar A[10], pot accesa elementele de la A[0] la A[9]

Codul lui wefgef este foarte bun si sunt sigur ca stie cum merg vectorii.. lucrul pe care l-a constat el este legat de if! Florin, nu ii trebuie vector de vector, pentru prima dimensiune stie exact dimensiunea necesare si nu iese din ea.. si eu sunt curios cum intretine indexarile (vectorul A[1] se redimensioneaza, cum mai stie cum sa acceseze A[2].. sau chiar A[1]?), dar se pare ca merge..
Singurul lucru mai "ciudat" este cum acel if da un rezultat odata si alt rezultat daca se folosesc variabile temporare pentru calculele intermediare -- singura diferenta pe care o vad eu este cea sugerata, cu variabile temporare fortezi sa faca calculele intr-o anumita ordine si comparatia sa fie intre inturi, altceva nu prea vad.
Ar mai putea fi pur si simplu un bug de compilator.. (binarul generat fara variabile temporare sa faca putin altfel calculele alea si sa le faca prost) :)

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Tofan Vasile din Ianuarie 14, 2007, 20:16:28
i see now. credeam ca vrea sa declare un vector de Lmax elemente de tipul pair<int, int>. :)

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Bogdan-Cristian Tataroiu din Ianuarie 14, 2007, 20:59:10
Un vector din stl nu e pur si simplu o zona continua de memorie... Pe langa elementele sale, se mai tin cateva variabile care nu se realoca... v._Myfirst (denumirea probabil variaza in functie de implementare) tine pointer catre zona continua de memorie in care sunt puse elementele vectorului.. si nu conteaza daca este realocata aceasta zona... v._Myfirst ramane in acelasi loc si nu sunt probleme daca tii un pointer la un vector stl :P... A[1] nu pointeaza pe elementele vectorului, ci pe acele variabile statice..

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Kerekes Felix din Ianuarie 15, 2007, 13:31:13
Ai incercat sa compilezi cu diferite nivele de opimizari? Poate da compilatorul rateuri..

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Andrei Grigorean din Ianuarie 15, 2007, 18:55:19
Citat din mesajul lui: Valentin Stanciu din Ianuarie 14, 2007, 18:04:34
wefgef, ai incercat sa pui paranteze? si sa faci type-casting?
Cod:
if ((int)(A[j-1][start[j-1]].x) > (int)(i-s[j-1].sz())) break;

 :D se pare ca asta era. Merge codul postat de tine :shock:

Titlul: Raspuns: cod c++ gresit (?)
Scris de: Andrei Grigorean din Ianuarie 17, 2007, 11:07:35
Am aflat de ce nu mergea :D. Se pare ca size() e unsigned. Pana la urma nu o lua pe aratura :P


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines