• 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
382 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,900 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,900 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,900 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,540 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,258 wizyt
pytanie zadane 12 maja 2015 w C i C++ przez Kabiszon Użytkownik (890 p.)
0 głosów
0 odpowiedzi 233 wizyt
pytanie zadane 31 grudnia 2022 w C i C++ przez Noizz00 Użytkownik (910 p.)
+2 głosów
2 odpowiedzi 320 wizyt
pytanie zadane 16 kwietnia 2021 w SPOJ przez manjaro Nałogowiec (37,390 p.)

92,454 zapytań

141,262 odpowiedzi

319,089 komentarzy

61,854 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

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

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!

...