Imprimă pagina - 1226 Planificare

Titlul: 1226 Planificare
Scris de: Andrei Grigorean din Ianuarie 22, 2012, 14:26:21

Aici puteÈ›i discuta despre problema Planificare (http://infoarena.ro/problema/planificare).

Titlul: RÄƒspuns: 1226 Planificare
Scris de: George Popoiu din Ianuarie 23, 2012, 17:36:41

Am folosit un multiset si cautare binara dar iau doar 40p cu TLE. Cred ca e de la metoda advance pe care o folosesc in cautarea binara. Pentru pozitia m, avansez iteratorul cu m pozitii. Fac ceva de genul

Cod:

it = T.begin();
advance(it, m);
int x = *it;

Pot sa fac ceva sa pastrez ideea asta si sa iau 100p ? Sau trebuie neaparat folosit lower_bound ?

Titlul: RÄƒspuns: 1226 Planificare
Scris de: Mihai Calancea din Ianuarie 23, 2012, 17:58:13

Pai analizeaza-ti putin complexitatea. Nu are niciun sens sa faci cautare binara pe o structura care nu iti permite acces indexat. Daca tie sa accesezi pozitia p iti trebuie O(p) timp n-ai rezolvat nimic. E mai rau decat daca faceai cautarea bruta, liniara. Fie folosesti lower_bound, fie iti faci arborele tau de cautare, dar iti dai seama ca nu prea merita. Ai sa gasesti alte probleme unde trebuie sa-l scrii de la 0 fiindca nu te ajuta set-ul.

Titlul: RÄƒspuns: 1226 Planificare
Scris de: Vlad Eugen Dornescu din Ianuarie 27, 2012, 10:14:39

As avea nevoie de putin ajutor la codul acesta :

Cod:

	fin >> n >> k;
	for(int i = 1; i <= n; i ++)
	fin >> t[i].start >> t[i].final;
	
	int ct = 1;
	int pred = 0;
	sort(t + 1, t + n + 1, cmp());
	spectacol.insert(t[1].final);

Primesc segmentation fault la linia cu

Cod:

 spectacol.insert(t[1].final)

Are cineva vreo idee de ce se intampla asta?
T e o structura cu final de tip int ... si multisetul e declarat multiset<int> spectacol;

Titlul: RÄƒspuns: 1226 Planificare
Scris de: Mircea Dima din Ianuarie 27, 2012, 16:54:15

Din cod nu pot trage nicio concluzie... pune toata sursa

Titlul: RÄƒspuns: 1226 Planificare
Scris de: Vlad Eugen Dornescu din Ianuarie 27, 2012, 18:37:27

Cod:

#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

const char iname[] = "planificare.in";
const char oname[] = "planificare.out";
multiset <int> spectacol;
multiset <int>::iterator it;

ifstream fin(iname);
ofstream fout(oname);

int n , k;

struct timp
{
	int final, start;
};

timp t[100002];
int ap[100002];


struct cmp 
{
	bool operator()(const timp &i, const timp &j)const
	{
		if(i.final > j.final)
			return 0;
		else
			if(i.final == j.final)
				if(i.start > j.start)
					return 0;
		return 1;
	}
};


int main()
{
	fin >> n >> k;
	for(int i = 1; i <= n; i ++)
	fin >> t[i].start >> t[i].final;
	
	int ct = 1;
	int pred = 0;
	sort(t + 1, t + n + 1, cmp());
	spectacol.insert(t[1].final);
	int i = 0, ocupate = 1;
	for(i = 2; i <= n; i ++)
	{
		it = spectacol.lower_bound(t[i].start);
		if(it != spectacol.begin() && *it > t[i].start)
			--it;
		if(*it < 0)
			it = spectacol.begin();
		if(*it <= t[i].start && *it > 0)
		{	
			spectacol.insert(t[i].final);
			spectacol.erase(it);
			++ct;
		}
		else
			if(ocupate < k)
			{
				ocupate ++;
				spectacol.insert(t[i].final);
				++ct;
			}
		
	}
		

	fout << ct << "\n";
	return 0;
}

Titlul: RÄƒspuns: 1226 Planificare
Scris de: Mircea Dima din Ianuarie 27, 2012, 19:02:35

Pe exemplu mie imi merge (gcc 4.2).
Am pus return 0 dupa primul insert in multiset si iti da incorect pe infoarena,altfel segfault.
Deci probabil in for-ul principal ai un bug.

Titlul: RÄƒspuns: 1226 Planificare
Scris de: Vlad Eugen Dornescu din Ianuarie 30, 2012, 11:37:21

Am descoperit ca problema era de la

Cod:

spectacol.erase(it);

. Acolo vreau sa sterg emisiunea la care o leg pe cea curenta (ca sa nu imi mai ramana in multiset si sa nu pot lega alte emisiuni de aceeasi emisiune). De la instructiunea aceea primesc KBS 6 SIGABRT. Se poate modifica valoarea de la adresa it intr-una cat mai mare ca sa evit problema fara sa folosesc functia erase()? #-o

Titlul: RÄƒspuns: 1226 Planificare
Scris de: Paul-Dan Baltescu din Ianuarie 30, 2012, 11:45:22

Incearca sa apelezi intai functia erase si apoi functia insert.

Titlul: RÄƒspuns: 1226 Planificare
Scris de: Vlad Eugen Dornescu din Ianuarie 30, 2012, 13:13:27

Citat din mesajul lui: FMI - Paul-Dan Baltescu din Ianuarie 30, 2012, 11:45:22

Incearca sa apelezi intai functia erase si apoi functia insert.

Cod:


if(*it <= t[i].start && *it > 0)        
{          
     spectacol.erase(it);           
     spectacol.insert(t[i].final);             
     ++ct;       
}

Am incercat acum, la fel KBS SIGABRT 6.

L.E : SOLVED - am rescris tot codul :)

Titlul: RÄƒspuns: 1226 Planificare
Scris de: Nicu B. din Septembrie 02, 2012, 16:15:28

Am facut asa:
Am bagat intr-un heap (sa-i zicem heap1) toate canalele.
Am sortat emisiunile crescator dupa timpul de incepere.
Pe rand, am bagat intr-un heap (sa-i zicem heap2) timpul de final al emisiunii curente si primul canal liber ( heap1.top() ), scotand din heap1 canalul, atat timp cat heap1 nu era gol.
La fiecare pas, scoteam din heap2 emisiunile terminate, introducand in heap1 canalele eliberate astfel.
Daca heap1 era gol, inseamna ca emisiunea curenta nu avea niciun canal disponibil deci nu se rula.

Nu inteleg de ce iau 0 pe ea (toate-s incorecte). Poate m-ati putea ajuta cu un test care sa-mi "explice" de ce solutia mea nu e buna :-"

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Ianuarie 22, 2012, 14:26:21