wniosek jest prosty. Te zadania są za proste i wszystko rozbija się o dokładność pomiarową.
Takie optymalizowanie operacji wejścia/wyjścia powoduje utratę całego sensu tych zadań, bo ludzie zamiast optymalizować rozwiązanie problemu w zasadzie optymalizują biblioteki C i C++, co nie ma sensu.
W sumie jestem ciekaw jak jest zrobiony ten system pomiarowy.
@...
0.092
#include <iostream>
#include <ios>
using namespace std;
int main()
{
int v,t;
ios_base::sync_with_stdio(false);
while ( cin >> v >> t )
{
cout <<(v<<1)*t <<endl;
}
return 0;
}
@MarekR22
Tylko początkowe zadania są proste i w.g. mnie kompletne bez sensu. Te trudniejsze są znacznie ciekawsze i w nich optymizacja czasowa tak naprawdę ma sens.
Ale prawda jest taka ze kluczowe jest znalezienie optymalnego algorytmu.
Jak ktoś ma rozwiazanie O(n^2) to choćby nie wiem jak cudowal z optymalizacją I/O, czy skracaniem obliczeń to nawet nie zbliży się do optymalnego rozwiazania O(nlogn).
Większość konkursów ma tak ustalone limity czasu ze rozwiązanie nieoptymalne po prostu nie przejdzie, niezależnie od tego jak ktoś będzie cudował, a optymalne przejdzie nawet korzystając ze strumieni.
Mówiąc krótko - przy każdym poważniejszym problemie koszt operacji nie związanych bezpośrednio z samym rozwiązaniem problemu jest pomijalny.
_asd napisał(a)
- nie używać nigdy zsynchronizowanego (czyli defaultowego) cin/cout
- w przypadku pracy z liczbami nie używać nigdy scanf(...) - zastąpić to własnym fragmentem kodu - ascii na int-y można przetworzyć w ten sposób o wiele szybciej /u mnie poprawiło to wynik o kilkanaście setnych ms);
- niczego nie mallocować - zazwyczaj spokojnie można zmieścić się w limitach pamięci deklarując tablice globalne.
- samemu formatować text wyjściowy i..
- ..jeśli to możliwe, batchować we własnej tablicy tekst wyjściowy i 'printować' go w 10 lub 100 partiach bez formatowania zamiast 10000-100000 razy z formatowaniem.
No i te rady okazały się stety/niestety trafiać w samo sedno :D
Różnice są od razu widoczne (między programami tutaj już umieszczonymi) co skłoniło mnie do implementacji "mini" klas do obslugi wejscia i wyjscia
z buforowaniem i własnym parserem
(kod wyszedl dosyck dlugi, ale wstawiam maly fragment)
#include <stdio.h>
#include <string.h>
#define max_buf_simpleinput 70
#define max_buf_simpleoutput 100000
//#define tryFlushing 1
class SimpleInput
{(...)};
class SimpleOutput
{(...)};
int main() {
static SimpleInput in;
static SimpleOutput out;
while (in.getLine())
{
out.putInt(in.nextInt()*in.nextInt()*2);
out.putChar('\n');
}
out.flush();
return 0;
}
Uzyskany czas to 0.012.
1.67 razy szybszy niz 'najszybszy' do tej pory kod
i 10 razy niż najwolniejszy
Nadal daleko do 0.00, ale nic nie było tablicowane tylko podrasowane samo i/o.
//Nie mozna, by bylo sprawdzac zadania na podstawie ile cykli procesora zabralo programowi dojscie do konca? bylo by to bardziej miarodajne, bo mozliwe jest, ze ludzie trafiaja na niski load :P