Hobbystyczne rozwiązywanie zadań... C++

Creeative

2012-08-23T15:25:09+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 34

0

Otóż mam takie pytanie, na main.edu.pl http://main.edu.pl/pl/user.phtml?op=showtask&task=prz&con=OIG6
wykonałem to, ale mam problem z przyśpieszeniem działania,
chciałbym się Was poradzić. Jestem początkujący w c++ więc nie ma mowy o jakiejś rozkminie.

Proszę Was tylko o naprowadzenie na błąd, lub na jakiś inny sposób.

Kopiuj

 #include <stdio.h>
using namespace std;

int main(){

    int n,m,p,ma=0;                     // n - liczba licznikow, m - liczba czynnosci, 
    scanf ("%d %d",&n,&m);          // p - numer licznika ( aktualnie podawany ), ma - indeks najwiekszego elementu
    int *tab = new int[n];
    for(int i=0; i<n; i++) tab[i]=0;   // Zerowanie wartości tablicy
    while ( m-- )
    {
        scanf("%d",&p);
        if ( p!=n+1 )
        {
            tab[p-1]++;
            if(tab[p-1]>tab[ma]) ma=p-1;
        }
        else
        {
            for(int i=0; i<n; i++)
            tab[i]=tab[ma];
        }
    }
    printf ("%d",tab[0]);
    for(int i=1; i<n; i++)
    {
        printf(" %d",tab[i]);
    }
    printf("\n");
    delete [] tab;
    return 0;
}

z góry dziękuje

darkfucker

2012-08-23T18:43:17+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 25

0

Po pierwsze - jeśli ta twoja stronka korzysta z ideone.com, to możesz spokojnie wywalić pierwszą pętlę for. Wejdź na ideone i skompiluj coś takiego:

Kopiuj

#include <iostream>
using namespace std;
int main ()
{
    int w = 10;
    int *x = new int [w];
    for(int i=0;i<w;i++) cout<<x[i]<<endl;
    delete [] x;
    return(0);
}

Po drugie - Gdzieś czytałem na spoju, że zamiast printf/scanf jest szybciej używać cout/cin razem z: ios_base::sync_with_stdio(0);

Rev

2012-08-23T19:02:56+02:00

Rejestracja: dni
Ostatnio: dni

0

delete[] może ci spowolnić cały program. Nic się nie zepsuje, jeżeli nie zwolnisz w tym wypadku pamięci.

Zadanie wygląda mi na jedno z tych, w których trzeba ostro optymalizować IO. W tym kierunku przeszukaj google.

hauleth

2012-08-23T19:33:59+02:00

Rejestracja: dni
Ostatnio: dni

0

Nie używaj w ogóle new w zadaniach konkursowych, w których liczy się czas. To nie są konkursy na których liczą się dobre praktyki, ładny kod czy piękne komentarze. Używasz zmiennych globalnych jeśli trzeba (sic!) jak np w tym przypadku.

Kopiuj

const unsigned int MAX_SIZE = 1000000;
unsigned int tab[MAX_SIZE];

W ten sposób masz tablicę od razu w pamięci (w przeciwieństwie do tablicy generowanej wewnątrz funkcji) i całą wyzerowaną za darmo i nie trzeba się babrać z zarządzaniem pamięcią.

BTW
To int n,m,p,ma=0; ustawi tylko zmienną ma na 0. Weź to wywal jako zmienne globalne wywal przypisanie. Masz je wyzerowane za darmo.

Xitami

2012-08-23T19:43:53+02:00

Rejestracja: dni
Ostatnio: dni

0

szkoda, że Spoj (ważny) ugrzązł w starych rozwiązaniach, nie pamiętam co ale zyskało wiele dzięki sztuczkom w I/O znacznie więcej niż w teoretycznie doskonalszym algorytmie. Przez chwilę chyba nawet dostali lepsze maszyny, tylko statystyki się posypały. Z drugiej strony np. project Euler. Tu ważna tylko odpowiedź.
Niby lepiej, ale szkoda że brak odrobiny rywalizacji.

Oak

2012-08-23T23:27:55+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 95

0

Gdy mamy liczbę n+1 zamiast za każdym razem modyfikować całą tablicę, możemy zapamiętać minimalną wartość pola. Przy próbie modyfikacji, sprawdzimy czy pole nie jest przypadkiem mniejsze od naszego minimum.

Kopiuj

#include <iostream>
#include <cstdio>
using namespace std;

void process(int nums[], int size) {
    int *numbers = nums-1;  // Tablica numbers numerowana jest od 1 do size
    int amount;
    scanf("%d", &amount);

    int min = 0;
    int max = 0;

    while (amount-- > 0) {
        int index;
        scanf("%d", &index);

        if (index > size) {
            min = max;
        } else {
            int &current = numbers[index];
            current = ((current < min) ? min+1 : current+1);
            if (max < current)
                max = current;
        }
    }

    for (int i = 1; i <= size; ++i)
        if (numbers[i] < min)
            numbers[i] = min;
}

int main() {
    static int numbers[1000000];
    int size;
    scanf("%d", &size);

    process(numbers, size);

    cout.sync_with_stdio(false);
    for (int i = 0; i < size; ++i)
        cout << numbers[i] << " ";
    cout << flush;

    return 0;
}

Rev

2012-08-24T00:34:33+02:00

Rejestracja: dni
Ostatnio: dni

1

Odpaliłem specjalny program optymalizacyjny w postaci trzech piw i z własnym IO zszedłem do sumy 0.73s ze wszystkich zestawów. I chyba przypomniałem sobie dlaczego nie lubię tych algorytmicznych zadań.

Kopiuj

#include <cstdio>
#include <cstring>

#define NUM_BUFFER_SIZE 7 // liczba 7-cyfrowa
#define BUFFER_SIZE 524288 + NUM_BUFFER_SIZE

void ProcessNumber(int buttonIdx);
int MyAtoi(char* buffer);

size_t counterCount;
int counters[1000000] = { 0 }, maxCounterValue = 0, latestOverrideValue = 0;

int main()
{
	static char buffer[BUFFER_SIZE];

	FILE *input = stdin, *output = stdout;

	size_t operationCount;
	fscanf(input, "%d %d\n", &counterCount, &operationCount);

	char numberBuffer[NUM_BUFFER_SIZE];
	int numBufIdx = 0;

	while(!feof(input))
	{
		int bytesRead = fread(buffer, 1, BUFFER_SIZE - NUM_BUFFER_SIZE, input);

		for(int i = 0; i < bytesRead; i++)
		{
			if(i == BUFFER_SIZE && buffer[i] != ' ')
				continue;

			if(buffer[i] != ' ')
			{
				numberBuffer[numBufIdx] = buffer[i];
				numBufIdx++;
			}

			if(buffer[i] == ' ' || (i == bytesRead - 1 && feof(input)))
			{
				numberBuffer[numBufIdx] = '\0';
				numBufIdx = 0;

				int number = MyAtoi(numberBuffer);
				ProcessNumber(number);
			}
		}

		if(numBufIdx != 0 && feof(input))
		{
			numberBuffer[numBufIdx] = '\0';

			int number = MyAtoi(numberBuffer);
			ProcessNumber(number);
		}
	}

	int bufferIdx = 0;
	numBufIdx = 0;
	for(int counterIdx = 0; counterIdx < counterCount; counterIdx++)
	{
		int number = counters[counterIdx];

		if(number < latestOverrideValue) number = latestOverrideValue;

		int j = 30;
		for(; number && j; --j, number /= 10)
			numberBuffer[NUM_BUFFER_SIZE - 2 - 30 + j] = number % 10 + '0';
		
		numberBuffer[NUM_BUFFER_SIZE - 1] = ' ';

		size_t numberBufStart = NUM_BUFFER_SIZE - (30 - j) - 1, numberBufLength = 30 - j + 1;

		memcpy(buffer + bufferIdx, numberBuffer + numberBufStart, numberBufLength);
		bufferIdx += numberBufLength;

		if(bufferIdx >= BUFFER_SIZE - NUM_BUFFER_SIZE)
		{
			fwrite(buffer, 1, bufferIdx, output);

			bufferIdx = 0;
		}
	}

	if(bufferIdx != 0)
		fwrite(buffer, 1, bufferIdx, output);

	return 0;
}

inline void ProcessNumber(int buttonIdx)
{
	if(buttonIdx == counterCount + 1)
		latestOverrideValue = maxCounterValue;
	else
	{
		int counterValue = counters[buttonIdx - 1];

		if(latestOverrideValue > counterValue)
			counters[buttonIdx - 1] = latestOverrideValue + 1;
		else
			counters[buttonIdx - 1]++;

		if(counters[buttonIdx - 1] > maxCounterValue)
			maxCounterValue = counters[buttonIdx - 1];
	}
}

inline int MyAtoi(char* buffer)
{
	int number = 0;

	for(int i = 0; buffer[i] != '\0' && buffer[i] != '\n'; i++)
	{
		number *= 10;
		number += buffer[i] - '0';
	}

	return number;
}