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

Обсуждение задачи 1386. И снова лабиринт

Why my code get TL?
Послано Felix_Mate 4 янв 2017 23:10
There is about nmax*nmax*smax=40 844 804 iterations and time must be about 0.1,0.2 sec. But program works >0.5 sec.
How I can to optimize my code?

const nmax=101;
      kmax=4;
      smax=4004;
      type myint=0..smax+1;
var
 ans:array[1..nmax,1..nmax] of boolean;
 count,s,t:myint;
 n,m,i,j,k,x,y,ii,jj:myint;
 command:array[1..nmax,1..nmax,1..kmax,1..2] of byte;
 memory:array[1..nmax,1..nmax,1..smax] of boolean;
 list:array[1..smax] of byte;

begin
 readln(n,m);

 for k:=1 to kmax do begin
  for i:=1 to n do begin
   for j:=1 to m do read(command[i,j,k,1],command[i,j,k,2]);
  end;
 end;

 read(s);
 for i:=1 to s do read(list[i]);

 for t:=1 to s do begin
  for i:=1 to n do begin
   for j:=1 to m do memory[i,j,t]:=false;
  end;
 end;

 count:=0;
 for i:=1 to n do begin
 for j:=1 to m do begin
  ans[i,j]:=false;
 end;
 end;

 for i:=1 to n do begin
 for j:=1 to m do begin
  t:=1;
  ii:=i;
  jj:=j;
  while(t<=s)and(not memory[ii,jj,t]) do begin
   memory[ii,jj,t]:=true;
   x:=command[ii,jj,list[t],1];
   y:=command[ii,jj,list[t],2];
   ii:=x;
   jj:=y;
   inc(t);
  end;
  if(t>s)and(not ans[ii,jj]) then begin
   inc(count);
   ans[ii,jj]:=true;
  end;
 end;
 end;

 writeln(count);
 for i:=1 to n do begin
 for j:=1 to m do begin
  if(ans[i,j]) then writeln(i,' ',j);
 end;
 end;
end.

Edited by author 04.01.2017 23:24
Now AC.
When I used a lot of memory, I got TL32. When I used a little memory, I got AC.Perhaps the cache helped.

Edited by author 23.06.2017 19:24