• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Optymalizacja kodu: Policzenie XOR na podanym przedziale

0 głosów
93 wizyt
pytanie zadane 2 października w C i C++ przez Michał F Nowicjusz (120 p.)

Oto treść zadania:
Jankowi, dzięki intensywnym przygotowaniom, udało się dostać do finału OMJ. Oczywiście jako finalista Olimpiady umie już dodawać, więc w ramach przygotowań do finału wymyślił sobie nowe ćwiczenie: zapisuje na
kartce n liczb, a następnie wybiera dwie liczby całkowite a, b i oblicza XOR wszystkich zapisanych liczb od a-tej
do b-tej włącznie.
Niestety, finał OMJ został odwołany, więc Janek nie będzie miał możliwości sprawdzenia swoich umiejętności
na zawodach. Pomóż mu i napisz program obliczający poprawne odpowiedzi.
WEJŚCIE
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i q (1 ¬ n, q ¬ 106
) oznaczające odpowiednio
ile liczb zapisał Janek na kartce i ile pytań chce zadać.
W drugim wierszu znajduje się n liczb całkowitych z przedziału h0, 106
i – liczby zapisane przez Janka na kartce.
W każdym z następnych q wierszy znajdują się dwie liczby całkowite a i b (1 ¬ a ¬ b ¬ n), które oznaczają
odpowiednio numer pierwszej i ostatniej liczby przedziału, na którym należy policzyć XOR.
WYJŚCIE
Należy wypisać odpowiedzi na kolejne pytania Janka, każde w oddzielnej linii.
PRZYKŁAD
Wejście:
6 2
31 13 16 21 0 1
1 6
2 5
Wyjście:
22
8

Oto mój kod, który otrzymuje 40 punktów:

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int t[n];
    for(int i = 0; i < n; i++){
        cin >> t[i];
    }
    int sp[n];
    sp[0] = t[0];
    for(int i = 1; i < n; i++){
        sp[i] = sp[i - 1] ^ t[i];
    }
    int a, b;
    while(m--){
        cin >> a >> b;
        if(a == 1){
            cout << sp[b-1] << endl;
        }
        else {
            cout << (sp[b-1] ^ sp[a-2]) << endl;
        }
    }
}

Przekroczony został limit czasu. Czy ktoś pomógłby mi zoptymalizować kod?

Nie chodzi o to, że używam cout zamiast printf itp.

komentarz 2 października przez Whistleroosh Nałogowiec (29,640 p.)

Spróbuj moze dodać to na początek maina:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

2 odpowiedzi

0 głosów
odpowiedź 2 października przez KumberTwo Dyskutant (8,260 p.)
Na pierwszy rzut oka wygląda to na zadanie z drzewem przedziałowym. Mógłbyś dać link do zadania?
1
komentarz 2 października przez Whistleroosh Nałogowiec (29,640 p.)
to jest klasyczne zadanie na xory na prefiksie, Drzewo przedziałowe to będzie overkill
komentarz 2 października przez KumberTwo Dyskutant (8,260 p.)
Fakt, zdecydowanine łatwiejszy i szybszy będzie sposób z prefiksami. Ciekawe czy drzewo przedziałowe weszłoby na 100
komentarz 2 października przez Whistleroosh Nałogowiec (29,640 p.)
Drzewo fenwicka powinno wejść na 100. No ale rozwiązanie które ma OP też powinno wejść na 100, a nie weszło, więc kto wie
komentarz 2 października przez Michał F Nowicjusz (120 p.)

@KumberTwZo, zadanko jest ze szkolnego sio2 i niestety nie mam jak dać linka. Jedyne co wiem, to to że w 3 z 5 testów limit czasu został przekroczony. Przyznam się szczerze, że nie wiem czym są drzewa przedziałowe. 

0 głosów
odpowiedź 3 października przez overcq Stary wyjadacz (14,310 p.)

Trochę na szybkości zyskuje się zależnie od danych następującym kodem

#include <iostream>
using namespace std;
 
int main(
){  int n, m;
    cin >> n >> m;
    int t[n];
    for( int i = 0; i != n; i++ )
        cin >> t[i];
    int a[m], b[m];
    int max = 1;
    for( int i = 0; i != m; i++ )
    {   cin >> a[i] >> b[i];
        if( b[i] > max )
            max = b[i];
    }
    int sp[max];
    sp[0] = t[0];
    for( int i = 1; i != max; i++ )
        sp[i] = sp[ i - 1 ] ^ t[i];
    for( int i = 0; i != m; i++ )
    {   int r;
        if( a[i] == 1 )
            r = sp[ b[i] - 1 ];
        else
            r = sp[ b[i] - 1 ] ^ sp[ a[i] - 2 ];
        cout << r << endl;
    }
}

Do testów kompilowany bez optymalizacji.

Podobne pytania

+1 głos
3 odpowiedzi 5,301 wizyt
pytanie zadane 12 maja 2015 w C i C++ przez Kabiszon Użytkownik (890 p.)
+2 głosów
2 odpowiedzi 81 wizyt
pytanie zadane 16 kwietnia w SPOJ przez manjaro Nałogowiec (34,960 p.)
+1 głos
2 odpowiedzi 159 wizyt
Porady nie od parady
Odznacz odpowiedź zieloną fajką, jeśli uważasz, że jest ona najlepsza ze wszystkich i umożliwiła ci rozwiązanie problemu.Najlepsza odpowiedź

85,698 zapytań

134,499 odpowiedzi

298,514 komentarzy

56,625 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...