Analiza programów

17.06.2009

Migający tłum

//Kamelneon? ;> Pozdrowienia dla Pana Rafala Nowaka! :D
#include <iostream>
#include <list>
using namespace std;
 
int dlugosci_cykli[100001];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    int a[n + 1];
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
 
    for (int i = 1; i <= n; i++)
    {
        if (dlugosci_cykli[i] == 0)
        {
           int dlugosc = 0;
           list < int > lista; //REV: a gdyby tak vector? i gdyby nie czyścić go, tylko zapisywać początek i koniec każdego cyklu? :)
           lista.push_back(i);
 
           int aktualny = a[i];
 
           while (aktualny != i)
           {
                 lista.push_back(aktualny);
                 aktualny = a[aktualny];
                 dlugosc++;
           }
 
           for (list < int > :: iterator it = lista.begin(); it != lista.end(); it++) //REV: podziwiam cierpliwość:) ja bym użył stosu albo vectora
               dlugosci_cykli[*it] = dlugosc;           
        }
    }
 
    int q;
    scanf("%d", &q);
 
    for (int i = 0; i < q; i++)
    {
        int ai, k;
        scanf("%d%d", &ai, &k);
 
        k = k % (dlugosci_cykli[ai] + 1); //REV: heurystyka fajna, ale poniżej O(n^2) nie zejdzie
 
        for (int j = 0; j < k; j++) //REV: to wygląda niedobrze wydajnościowo :)
            ai = a[ai];
 
        printf("%d\n", ai);
    }
 
    return 0;
}
 

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com