Zadanie pracownik

Siema! Rozwiązuje zadanie na uczelnie, teoretycznie juz rozwiązałem ale system nie chce przepuścić ze względu na przekroczenie limitu pamięciowego:

Ogólnie w zadaniu chodzi o to, że jest N liczby zadań, każdy ma Z "priorytet"(tzn. im większa cyfra tym ważniejsze zadanie). W przypadku kiedy jest 0, oznacza to ze bedzie wybierane jedno zadanie z tych ktore sa (na lewo od 0, mniejsze indeksy). Trzeba pamietac ze 0 nie sa liczone do numeru zadania, czyli wyjscia. Tutaj przykładowe wejscie / wyjście:

Wejście:
7
3 0 0 2 8 8 0

Wyjście:  // wyjsciem jest numer zadania, zaczynamy od 1
1
3  // jest 3, mimo tego ze 8 jest na 5 pozycji, nie liczymy 0

 
Wejście2:
10
1 1 1 1 2 0 0 0 0 0

Wyjście2:
5  // najpierw zadanie o priorytecie 2
1 // i dalej 1 , ta ktora pierwsza jest brana
2
3
4

#include  <stdio.h>

int main(){
	int N;
	int Z; 
	scanf("%d", &N);
	int przesuniecie;
	int t[N];
	int t_bez[N];
//	int index;
	for(int i = 0; i < N; i++){ 
		scanf("%d", &Z);
		t[i] = Z;
		t_bez[i] = Z;
	}
	
				
		
	for(int i = 0; i < N; i++){  

			
		int maximum = t[i];
		int pozycja = 1;
		if(t[i] == 0){ 
		
		int index_0 = i;		

			
		for(int c = 0; c < i; c++){ 
			
			if (t[c] > maximum)  //&& t[c] >= 0
			{
				maximum = t[c];
				pozycja = c + 1;
			}
		}
		if(t[pozycja - 1] > 0){
			
			for(int j = pozycja - 1; j > 0; j--){
				
				if(t_bez[j] == 0){
			 		przesuniecie += 1;
												
				}
			}
			
			printf("%d\n", pozycja - przesuniecie);
		}
		t[pozycja - 1] = -1;
		przesuniecie = 0;
		}
		
		
	}
	return 0;
}

A tu kod (nie chce go dzielic na funkcje)

To w końcu co? przekraczasz limit pamięciowy czy czasowy?
Jaki jest limit na N?
C czy C++ (kod masz w C a dałeś tag-a C++).

1. Stwórz sobie strukturę (index, pririority), żeby ograniczyć: cache miss.
2. Przetwarzaj dane na bieżąco, jak napotkasz zero to usuń z kolejki zadanie (zanim wstawisz kolejne zadanie)
3. Na podstawie limitu pamięci policz sobie jak wielką tablicę możesz zbudować (pewnie ma być mniej niż N).

Może stwórz kolejkę priorytetową - kopiec, ładuj kolejne liczby do niej razem z numerem pozycji w ciągu, aż do napotkania zera, wtedy kolejno wyciągasz z kopca liczby od największej do najmniejszej. Po wyczyszczeniu kopca czytasz i pomijasz kolejne zera, a po napotkaniu liczby różnej od zera, powtarzasz cały proces od początku.

A masz jakieś limity na wartości Z?
Bo jeśli wartości są małe to wystarczy zmapować kolejki FIFO z wartościami Z (szybciej się nie da).

#include  <stdio.h>


struct zadanie {
	int priorytet;
	int index;
	int t_bez;
};


int main(){
	int N;
	int Z;
	int przesuniecie;
	scanf("%d", &N);
	struct zadanie pracownik[N];
	for(int i = 0; i < N; i++){ 
		scanf("%d", &Z);
		pracownik[i].priorytet = Z;
		pracownik[i].index = i + 1;
		pracownik[i].t_bez = Z;
	}
	
	for(int i = 0; i < N; i++){

			
		int maximum = pracownik[i].priorytet;
		int pozycja = 1;
		if(pracownik[i].priorytet == 0){ 
							
		for(int c = 0; c < i; c++){ 
			
			if (pracownik[c].priorytet > maximum)  
			{
				maximum = pracownik[c].priorytet;
				pozycja = pracownik[c].index;
			}
		}
		if(pracownik[pozycja - 1].priorytet > 0){
			
			for(int j = pozycja - 1; j > 0; j--){
				
				if(pracownik[j].t_bez == 0){
			 		przesuniecie += 1;
												
				}
			}
			printf("%d\n", pozycja - przesuniecie);
		}
		pracownik[pozycja - 1].priorytet = -1;
		przesuniecie = 0;
		}
			
	}
	return 0;
}

Zrobilem to w ten sposob i jest dalej przekroczenie czasowe.. :P

Wklejam jak wyglada tresc zadania:

Teodor nie lubi siedzieć w swoim biurze, gdzie w każdej chwili może pojawić się szef i kazać mu wykonać jakieś zadanie. W związku z tym po przyjściu do pracy włącza komputer, wiesza płaszcz na wieszaku i wymyka się z budynku. Szef jest przekonany, że Teodor jest gdzieś w firmie, ale zorientował się już, że zwykle trudno go znaleźć. Kiedy ma dla niego zadanie, nawet nie próbuje go szukać, tylko zostawia mu na biurku potrzebne materiały i informację o priorytecie zadania. Czasem Teodora dopadają wyrzuty sumienia. Wraca wtedy do biura i jeśli czekają na niego jakieś zadania, to wykonuje to z nich, które ma najwyższy priorytet. Jeśli jest kilka zadań o najwyższym priorytecie, to wybiera to z nich, które otrzymał najwcześniej. Po wykonaniu jednego zadania lub jeśli nie ma żadnych dostępnych zadań, Teodor uznaje się za pracowitego człowieka i ponownie wychodzi z biura.

Wiedząc, jakie zadania przygotował szef oraz kiedy Teodor pojawiał się w biurze, sprawdź, które zadania zostały wykonane.

Wejście

Pierwsza linia wejścia zawiera liczbę N oznaczającą liczbę wydarzeń w biurze Teodora (N<=100 000). Druga linia zawiera N liczb całkowitych Z opisujących kolejne wydarzenia (0<=Z<=1000). Jeśli Z jest dodatnie, oznacza to, że szef zlecił Teodorowi zadanie o priorytecie Z. Jeśli Z jest równe 0, to Teodor przyszedł do biura sprawdzić, czy są jakieś zadania.

Wyjście

Wypisz w osobnych liniach numery zadań, które kolejno wykonał Teodor. Zadania numerowane są od 1, w kolejności, w jakiej zostały zadane.

Twój algorytm jest naiwny i ma złożoność pesymistyczną o(n^2).
Ten problem spokojnie da się rozwiązać ze złożonością o(n log max(z)), a nawet o(n).

Napisz sobie kolejkę FIFO dla int-ów (indeksy).
Napisz sobie drzewo binarne dla priorytetów Z jako klucz i wartością niech będzie kolejka FIFO indeksów.
Jak odczytasz zadanie o Z!=0 to sprawdzasz czy drzewo zawiera już ten klucz. Jeśli nie dodajesz ten klucz z pustą kolejką FIFO.
Do tej kolejki dodajesz wartość.
Jeśli odczytasz wartość Z==0 to bierzesz skrajny element drzewa (największy klucz/priorytet), wyciągasz zawartej tam kolejki FIFO wartość i ją wyświetlasz.
Jeśli wielkość FIFO spadnie do zera to usuwasz klucz z drzewa.

#include  <stdio.h>
int main(){
	int N;
	int Z; 
	scanf("%d", &N);
	int t[100000];	
	int zero = 0;
	int pozycja;
	for(int i = 0; i < N; i++){ 
		scanf("%d", &Z);
		if(Z != 0)
			t[i - zero] = Z;		
		if(Z == 0){
			zero += 1;
			int maximum = t[i];	
			for(int c = 0; c < i; c++){ 		
				if (t[c] > maximum)
				{
					maximum = t[c];
					pozycja = c + 1;
				}				
			}
			if(t[pozycja - 1] > 0)
				printf("%d\n", pozycja);
			t[pozycja - 1] = -1;
			}
	}
}

Ma ktos jakis pomysl co tutaj jest zbedne jeszcze?

Pakując wszystko w main nigdy tego nie zrobisz.
Każdy problem trzeba dzielić na mniejsze i zamykać je w swoich funkcjach.

Zacznij od czegoś takiego:

struct FifoInt {
    int first;
    int last;
    int buffSize;
    int *buff;
};

typedef struct FifoInt *FifoIntRef;

void FifoIntInit(FifoIntRef fifo, size_t size)
{
    fifo->first = 0;
    fifo->last = 0;
    fifo->buffSize = size;
    fifo->buff = malloc(sizeof(int) * size);
}

void FifoIntDeinit(FifoIntRef fifo)
{
    fifo->first = 0;
    fifo->last = 0;
    fifo->buffSize = 0;
    free(fifo->buff);
}

// resztę rób sam:
void FifoIntDoubleResize(FifoIntRef fifo); // potrzebne gdy bufor jest zapełniony, a trzeba dodawać element 
void FifoIntEnqueue(FifoIntRef fifo, int x); // x nie może być równe zero
int  FifoIntDequeue(FifoIntRef fifo); // 0 - brak wartości (pusta kolejka), != 0 nr zadania
int  FifoIntIsEmpty(FifoIntRef fifo);

Raczej chodzi o to, żebyś popisał podstawowe rzeczy, zamiast korzystać z bibliotek.
W C++ może to wyglądać tak: https://wandbox.org/permlink/FBNLtgbriWQt5NgU