ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1024. Перестановки

TLE at test#11
Послано Madhav 17 июн 2008 17:22
I am getting time limit exceeded using a naive method.How can i write better program.pls some one help me.
this is my code

#include<iostream>
using namespace std;
int n;
int main(){
        cin>>n;int k=1;int i;
        int *a=new int[n+1];
        int *b=new int[n+1];
        int *c=new int[n+1];
        for(i=1;i<=n;i++){
                cin>>a[i];
                b[i]=a[i];
        }
        while(1){
                for(i=1;i<=n;i++)
                        if(b[i]!=i)
                                break;
                if(i==n+1){
                        cout<<k<<endl;
                        break;
                }
                for(i=1;i<=n;i++)
                        c[i]=b[i];
                for(i=1;i<=n;i++){
                        b[i]=c[a[i]];
                }
                k++;
        }
        return 0;
}
Re: TLE at test#11
Послано Vedernikoff Sergey 18 июн 2008 02:39
Answer can be up to 10^9, and it is fairly easy to construct such a test - so, try to develop a math solution in O(N)
Re: TLE at test#11
Послано Madhav 19 июн 2008 23:50
All of them using something like gcd and lcm.Can u tell me the idea.