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

Обсуждение задачи 1037. Управление памятью

What the might me wrong with this solution and why do I keep getting WA
Послано Alexander Mavrov 16 авг 2002 06:28
#include <stdio.h>

#define MAXC 30300
#define TL 600

int t,n,last[MAXC],inh[MAXC],hc=0,heap[MAXC];
char c;

int greater(int i,int j){
    if(last[heap[i]]>last[heap[j]]) return 1;
    if(last[heap[i]]<last[heap[j]]) return 0;
    if(heap[i]>heap[j]) return 1;
    return 0;
}

void __swap__(int& i,int& j){
    int tmp = i;
    i = j;
    j = i;
}

void __swap(int i,int j){
    __swap__(inh[heap[i]],inh[heap[j]]);
    __swap__(heap[i],heap[j]);
}

void heapify(int x){
    if(x*2>hc) return;
    if(x*2==hc){
        if(greater(x,x*2)) __swap(x,x*2);
        return;
    }
    if(greater(x*2+1,x*2)){
        if(greater(x,x*2)){
            __swap(x,x*2);
            heapify(x*2);
        }
    }else{
        if(greater(x,x*2+1)){
            __swap(x,x*2+1);
            heapify(x*2+1);
        }
    }
}

int getfree(){
    if(hc==0){
        last[1] = t;
        heap[1] = 1;
        hc = 1;
        inh[1] = 1;
        return 1;
    }
    if((t-last[heap[1]])<TL){
        hc++;
        inh[hc] = hc;
        heap[hc] = hc;
        last[hc] = t;
        return hc;
    }
    int tmp = heap[1];
    last[heap[1]] = t;
    heapify(1);
    return tmp;
}

void main(){
    for(n=1;n<=MAXC;n++) last[n] = -1000;
    while(scanf("%d",&t)!=EOF){
        do{
            scanf("%c",&c);
        }while(c!='.'&&c!='+');
        if(c=='.'){
            scanf("%d",&n);
            if((t-last[n])<TL){
                printf("+\n");
                last[n] = t;
                heapify(inh[n]);
            }else printf("-\n");
        }else{
            printf("%d\n",getfree());
        }
    }
}