2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Блокировки
Сообщение16.06.2017, 13:58 


04/05/13
125
Кажется, я немного облажался с сортировкой.. :oops: сейчас исправлю

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 13:59 
Заслуженный участник
Аватара пользователя


01/09/13
4318
inky в сообщении #1226101 писал(а):
Исправил :-)

Ну два условия в if, а не 4!....

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 14:03 
Заслуженный участник


04/03/09
906
Geen в сообщении #1226112 писал(а):
Необязательно. Нужно только если возникает пересечение с добавляемой.
Согласен. В худшем случае, у нас всем равно будут в структуре сидеть все блокировки, и тогда удаление старых - это лишняя операция (но худший случай для неудаления старых и худший случай для удаления старых - это разные худшие случаи). А вот что будет выгоднее в среднем - пока не знаю. С одной стороны, если не удалять просроченные, это минус одна операция, с другой стороны, если удалять просроченные, у нас будет меньше элементов в структуре, что определенно плюс.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 14:05 
Заслуженный участник
Аватара пользователя


01/09/13
4318
12d3 в сообщении #1226118 писал(а):
у нас будет меньше элементов в структуре, что определенно плюс.

Если поиск логарифмичен это не очень критично...

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 14:14 
Заслуженный участник


04/03/09
906
Geen в сообщении #1226121 писал(а):
Если поиск логарифмичен это не очень критично...

Хех, я опять накосячил. Ведь у нас сортировка не по времени а по границам ресурсов. Так что поиск старых в любом случае линейный, что сводит все плюсы сета на нет. Значит, не нужно специально искать старые.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 14:43 


04/05/13
125
Geen в сообщении #1226117 писал(а):
Ну два условия в if, а не 4!....

:oops:
Используется синтаксис C++
if (!(it->end < start) &&
    !(it->start > end)) {
    cout << "No";
    return 1;
}
 


-- 16.06.2017, 16:54 --

Не могу понять, где я теперь накосячил....неверный ответ на 7-ом тесте. Видимо, какие-то активные блокировки остаются в хвосте. Функция insert вроде как добавляет элемент перед итератором.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>
#include <list>

using namespace std;

struct block {
    int start, end, time;
};

int block_me(list<block> *blocked, int time, int start, int end, int duration) {
    list<block>::const_iterator spot = blocked->cbegin();
   
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            break;
        }
        if (it->time > spot->time) {
            spot = it;
            ++spot;
        }
       
        if (!(it->end < start) &&
            !(it->start > end)) {
            cout << "No";
            return 1;
        }
    }
   
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->insert(spot, t);
   
    cout << "Yes";
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    list<block> blocked;
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        block_me(&blocked, s, l, r, d);
        cout << endl;
    }
   
    return 0;
}
 


-- 16.06.2017, 17:13 --

Все, понял где облажался. И исправил.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>
#include <list>

using namespace std;

struct block {
    int start, end, time;
};

int block_me(list<block> *blocked, int time, int start, int end, int duration) {
    list<block>::const_iterator spot = blocked->cbegin();
   
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            break;
        }
        if (it->time > time + duration) {
            spot = it;
            ++spot;
        }
       
        if (!(it->end < start) &&
            !(it->start > end)) {
            cout << "No";
            return 1;
        }
    }
   
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->insert(spot, t);
   
    cout << "Yes";
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    list<block> blocked;
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        block_me(&blocked, s, l, r, d);
        cout << endl;
    }
   
    return 0;
}
 


-- 16.06.2017, 17:37 --

Снова застрял..не проходит ограничение по времени на 17-ом тесте :cry:

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 15:40 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
На каких языках там можно писать? Java или паскаль в списке доступных есть? Тоже что ли попробую :mrgreen:

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 15:45 


04/05/13
125
rockclimber
Можно. Вот ссылка. Задача E.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 16:11 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
inky
"У вас нет прав просматривать это соревнование"
Надо предварительно другие задания пройти?

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 16:53 


04/05/13
125
rockclimber
Это были задачки на стажировку, регистрация на которую уже закрыта. :roll:

-- 16.06.2017, 18:54 --

Я не смог решить эту задачу с блокировками и теперь она не дает мне покоя :-)

-- 16.06.2017, 19:07 --

Geen, 12d3 я попробовал реализовать через set. Но, похоже, что-то не учел, программа выдает неверный ответ на 9-ом тесте..
Почитал документацию к set, переписал оператор "<" так, чтобы для неподходящей блокировки
Код:
!comp(a, b) && !comp(b, a) == true
.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>
#include <set>

using namespace std;

class Block {
    int start, end, time, duration, expires;
   
public:
    Block(int time, int start, int end, int duration) : start(start), end(end), time(time), duration(duration), expires(time + duration) {}
   
    Block() {}
   
    Block& operator=(const Block& r) {
        this->time = r.time;
        this->start = r.start;
        this->end = r.end;
        this->duration = r.duration;
        this->expires = r.expires;
        return *this;
    }
   
    bool operator<(const Block& r) const {
        Block first, second;
        if (this->time < r.time) {
            first = *this;
            second = r;
        } else {
            first = r;
            second = *this;
        }
       
        if (first.expires > second.time &&
            !(first.end < second.start) &&
            !(first.start > second.end)) {
            return false;
        }
       
        return first.time < second.time;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    set<Block> blocked;
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        Block t(s, l, r, d);
        auto res = blocked.insert(t);
        if (res.second) {
            cout << "Yes";
        } else {
            cout << "No";
        }
        cout << endl;
    }

    return 0;
}
 

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 17:51 
Заслуженный участник


04/03/09
906
inky
Так можно сортировать просто по левой границе занимаемых ресурсов, т.е. по возрастанию start. И будем следить, чтобы у блокировок, которые находятся в множестве, промежутки $[start;end]$ не пересекались. Делаем примерно так:
На этапе проверки на пересечение с имеющимимся блокировками, ищем наименьший элемент, у которого start больше вставляемого, а также наибольший элемент, у которого start меньше вставляемого. Если эти товарищи пересекаются (как прямоугольники), то не вставляем. А если не пересекаются прямоугольники, но пересекаются "в проекции" на ось ресурсов, то удаляем старый(е) и вставляем новый. А если даже в проекции не пересекаются, то просто вставляем.
UPD. Конечно же, проверять на пересечение надо не только найденные в множестве наибольший и наименьший, но и все между ними.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 18:09 
Заслуженный участник
Аватара пользователя


01/09/13
4318
inky в сообщении #1226208 писал(а):
попробовал реализовать через set.

Просто set не поможет (на множестве отрезков у нас не полное упорядочивание).
Возможно надо самому реализовать какое-нибудь достаточно сбалансированное дерево с эффективным блочным удалением...
Только всю память надо выделять один раз в начале.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 18:13 


04/05/13
125
12d3
Чуть позже попробую реализовать.

Geen
Я надеюсь, что не придется самому писать дерево :roll:

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 18:37 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Кстати, а сколько бит там int?

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 18:48 


04/05/13
125
Geen
Не меньше 16 бит. На 64-разрядных обычно 32 бита.

-- 16.06.2017, 20:50 --

12d3
Реализовал, но определенно где-то закралась ошибка: runtime error на седьмом тесте.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>
#include <set>

using namespace std;

class Block {
    int start, end, time, duration, expires;
   
public:
    Block(int time, int start, int end, int duration) : start(start), end(end), time(time), duration(duration), expires(time + duration) {}
   
    Block() {}
   
    Block& operator=(const Block& r) {
        this->time = r.time;
        this->start = r.start;
        this->end = r.end;
        this->duration = r.duration;
        this->expires = r.expires;
        return *this;
    }
   
    bool operator<(const Block& r) const {
        return this->start < r.start;
    }
   
    bool intersects(Block bl) const {
        if (!(this->end < bl.start) &&
            !(this->start > bl.end) &&
            ((this->time < bl.time && this->expires > bl.time) ||
             (bl.time < this->time && bl.expires > this->time))) {
            return true;
        }
        return false;
    }
   
    bool resources_intersect(Block bl) const {
        if (!(this->end < bl.start) &&
            !(this->start > bl.end)) {
            return true;
        }
        return false;
    }
};

bool insert(set<Block> *blocked, Block bl) {
    set<Block>::iterator up = blocked->upper_bound(bl), low;
    if (up != blocked->end() || !blocked->empty()) {
        low = prev(up);
    } else {
        low = up;
    }
   
    if ((low != blocked->end() && low->intersects(bl)) ||
        (up != blocked->end() && up->intersects(bl))) {
        return false;
    }
   
    if (low != blocked->end() && low->resources_intersect(bl)) {
        blocked->erase(low);
    }
   
    if (up != blocked->end() && up->resources_intersect(bl)) {
        blocked->erase(up);
    }
   
    blocked->insert(bl);
   
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    set<Block> blocked;
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        Block t(s, l, r, d);
        if (insert(&blocked, t)) {
            cout << "Yes";
        } else {
            cout << "No";
        }
        cout << endl;
    }
   
    return 0;
}
 

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 53 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group