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

Обсуждение задачи 1251. Менеджер кладбища

To anyone got 'time limted': could you show your program?
Послано Lin 22 мар 2003 19:04
<P><P><P>: could you show your TL program?
Послано Lin 24 мар 2003 20:14
>
I got TLE. I did the same thing, but in a faster way and I got WA (maybe it passed the tests this program got TLE and still got WA)
Послано Scythe (Berinde Radu) 24 мар 2003 20:17
#include <stdio.h>
#include <stdlib.h>

#define T1 1000
#define T2 100
#define NVEC 8

#define INF 66666
int Lasttime[10010];
int Clients;
int Empty[10010], Canmove[10010];
#define time(i, j) (Time - Lasttime[Cl[i][j]])

int vi[8] = {0, 0, -1, 1, 1, -1, 1, -1};
int vj[8] = {1, -1, 0 ,0, -1, 1, 1, -1};
#define ni (i + vi[v])
#define nj (j + vj[v])

int Cl[210][210], N, M;
int Time;

void read_and_solve()
{
    int i, j, x, v, fnd, Res = 0;
    char a;
    scanf("%d %d", &N, &M);
    Lasttime[0] = -INF;
    while (scanf("%d %c", &Time, &a) == 2)
    {
        if (a == 'v')
        {
            scanf("%d", &x);
            if (!Empty[x]) Lasttime[x] = Time;
            continue;
        }
        for (i = 1; i <= N; i++)
         for (j = 1; j <= M; j++)
         if (Cl[i][j] && (!Empty[Cl[i][j]] || !Canmove[Cl[i][j]]))
         {
             if (time(i, j) > T1) Empty[Cl[i][j]] = 1;
             for (v = 0; v < NVEC; v++)
                 if (ni > 0 && nj > 0 && ni <= N && nj <= M &&
                     Cl[ni][nj] && time(ni, nj) <= T2)
                     break;
             if (v == NVEC) Canmove[Cl[i][j]] = 1;
         }
        Lasttime[++Clients] = Time;
        for (fnd = 0, i = 1; !fnd && i <= N; i++)
         for (j = 1; !fnd && j <= M; j++)
          if (Cl[i][j] == 0 || (Empty[Cl[i][j]] && Canmove[Cl[i]
[j]]))
                 Cl[i][j] = Clients, fnd = 1;

        if (!fnd) Res++;
    }
    printf("%d\n", Res);
}

int main()
{
    read_and_solve();
    return 0;
}
I agree with you,the tests may be wrong.
Послано Lin 25 мар 2003 16:50
Re: Sorry, no. But I must say, that I use n*log(n) and I'm shure my TL isn't because of bad complexity.
Послано <P><P><P> 26 мар 2003 15:50
> >