WPC-Aufgabe (Programmierwettbewerb)

[Michael E.]

Ich komm auch auf 290 Dann kann ich ja mal anfangen, die Implementierung zu verbessern.

[angeber]

Bin auf 180

[Michael E.]

#include <algorithm>

#pragma warning(push) 
#pragma warning(disable:4035) 
u64 rdtsc() 
{ 
	__asm rdtsc; 
} 
#pragma warning(pop)

int main()
{
	u64 sum = 0;
	u64 time;

	std::vector<unsigned int> origin;
	for(unsigned int i = 0; i < 10000000; ++i)
        origin.push_back(i);

    std::random_shuffle(origin.begin(), origin.end());

    std::cout << "initialized" << std::endl;

    for(int i = 0; i < 10000; ++i)
    {
    	std::vector<unsigned int> weights(origin.begin() + i*1000, origin.begin() + (i+1)*1000);

		time = rdtsc();

        wpc_expert(weights);

        sum += rdtsc() - time;
    }

    std::cout << (sum / 10000) << std::endl;

    sum = 0;

    for(int i = 0; i < 100; ++i)
    {
    	std::vector<unsigned int> weights(origin.begin() + i*100000, origin.begin() + (i+1)*100000);

    	time = rdtsc();

    	wpc_expert(weights);

    	sum += rdtsc() - time;
    }

    std::cout << (sum / 100) << std::endl;
}

Kompiliert mit VC++ 2003 Toolkit auf Speed optimiert komm ich auf folgende Ausgabe:

5 174 824
722 308 723

Wie siehts bei euch aus?

[wtf!]

Michael E. was soll der Mist? Deine Lösung soll geheim bleiben.

[Michael E.]

Troll.

[TomasRiker]

Darf man eigentlich hash_map etc. verwenden oder muss man alles selbst programmieren?

[ERROR]

hi

zur sortieraufgabe:

das mit den 290 kann ich irgend wie nicht richtig glauben

keine kiste ist am richtigen platz, also muss jede mindestens einmal bewegt werden, macht 286 ... dann bleiben also nurnoch 4 übrig, d.h. entweder wird die 4 ein zweites mal verrückt oder ihr verrückt die 1 und die 3 je zweimal oder ihr verrückt fünf mal die 1 ... anders gehts ja nicht ... nur wie sieht das bei euch aus?

welche variante entsteht bei euch?

danke und schönen zweiten weihnachtstag noch
:xmas2: andy :xmas1:

[Gast]

Doch, 290 geht. Das hab ich natürlich auch von Anfang an gehabt, 304 war nur, um euch zu foppen.

[ERROR]

jupp ok habs auch: 5 mal die 1

cu

[Jester]

Klar, Standard-Lib ist erlaubt! Ja, die getter/setter müssen natürlich const sein.
Ich änder's gleich noch in der Aufgabenstellung.

Die Geschenke haben natürlich alle ein Gewicht echt größer 0.

MfG Jester

[Michael E.]

Jester schrieb:

Klar, Standard-Lib ist erlaubt!

hash_map ist doch aber nur ne standard extension, oder etwa nicht?

[Jester]

Ist auch wieder wahr. Aber wenn ne Hashmap hilft, dann soll's mir recht sein.

[Gast]

Was ist die Referenz, ob das Programm standardkonform genug ist? Ich kann beim VC++ 8 size_t benutzen ohne std:: ist das normal?

[TomasRiker]

Also ich denke mal nicht, dass Du mit einer Strafe rechnen musst, wenn noch ein "std::" irgendwo vor muss

[Jester]

Wenn da sowas wie ein std:: fehlt, dann ist das kein Problem. Ich prüfe sicher nicht jedes Detail nach.

Nur, wenn ich das nicht mit geringem Aufwand kompiliert krieg (weil grobe Syntaxfehler drin sind), dann werde ich's halt rausschmeißen.

[Jester]

@Korrektheit: Mit der Formulierung wollte ich aussagen, daß die Lösung natürlich korrekt arbeiten muß und andernfalls ausgeschlossen wird.

[TomasRiker]

Mein Algorithmus läuft mit Visual C++ (STLPort) mehr als doppelt so schnell als mit GCC... liegt das eher an der STL-Implementierung oder an was anderem?

[TGGC|_work]

TomasRiker schrieb:

Mein Algorithmus läuft mit Visual C++ (STLPort) mehr als doppelt so schnell als mit GCC... liegt das eher an der STL-Implementierung oder an was anderem?

Profiler.

[User--]

hash_map ist nen bischen ungeschickt, da viele Standard-Libs die zwar anbieten, aber oft nen anderes Interface haben.
Wäre es daher nicht klüger zu sagen, alle sollen STLPort verwenden?

[Gast]

Ne, darauf hab ich keine Lust. Im Zweifelsfall würde ich halt sagen, er muss die nötigen Header für hash_map mitliefern.