• 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

VPS Starter Arubacloud
0 głosów
485 wizyt
pytanie zadane 2 października 2021 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 2021 przez Whistleroosh Maniak (56,980 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 2021 przez KumberTwo Dyskutant (8,270 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 2021 przez Whistleroosh Maniak (56,980 p.)
to jest klasyczne zadanie na xory na prefiksie, Drzewo przedziałowe to będzie overkill
komentarz 2 października 2021 przez KumberTwo Dyskutant (8,270 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 2021 przez Whistleroosh Maniak (56,980 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 2021 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 2021 przez overcq Pasjonat (21,860 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 7,471 wizyt
pytanie zadane 12 maja 2015 w C i C++ przez Kabiszon Użytkownik (890 p.)
0 głosów
0 odpowiedzi 308 wizyt
pytanie zadane 31 grudnia 2022 w C i C++ przez Noizz00 Użytkownik (910 p.)
+2 głosów
2 odpowiedzi 341 wizyt
pytanie zadane 16 kwietnia 2021 w SPOJ przez manjaro Nałogowiec (37,390 p.)

92,770 zapytań

141,695 odpowiedzi

320,518 komentarzy

62,107 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...