2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: Блокировки
Сообщение16.06.2017, 18:52 
Заслуженный участник
Аватара пользователя


01/09/13
4318
inky в сообщении #1226275 писал(а):
Не меньше 16 бит.

Мало... И для $10^5$, и тем более для $10^9$...

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


04/03/09
906
inky в сообщении #1226275 писал(а):
Реализовал, но определенно где-то закралась ошибка
Я чуть позже добавил в свой пост.
12d3 в сообщении #1226243 писал(а):
UPD. Конечно же, проверять на пересечение надо не только найденные в множестве наибольший и наименьший, но и все между ними.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 18:57 
Аватара пользователя


31/03/13
25
Есть специальная структура данных для работы с отрезками — дерево отрезков. Эта задача как раз про неё.

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


04/05/13
125
quartermind
Спасибо, чуть позже почитаю.

12d3
Наверное, буду исправлять уже завтра. Надеюсь, сработает.

-- 16.06.2017, 21:13 --

Geen в сообщении #1226277 писал(а):
Мало... И для $10^5$, и тем более для $10^9$...

Действительно :facepalm: Исправил везде на long int.

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


01/09/13
4318
quartermind в сообщении #1226280 писал(а):
Есть специальная структура данных для работы с отрезками — дерево отрезков. Эта задача как раз про неё.

Ну нельзя же так сразу... :mrgreen:
Кстати, а к тестовым наборам у Вас, случайно, нет доступа? :-)

-- 16.06.2017, 23:55 --

inky в сообщении #1226287 писал(а):
Спасибо, чуть позже почитаю.

Лучше пока не читайте... :-)

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


04/05/13
125
Geen в сообщении #1226414 писал(а):
Лучше пока не читайте... :-)

Почитал, но вникнуть времени не было :cry:

Geen в сообщении #1226414 писал(а):
Кстати, а к тестовым наборам у Вас, случайно, нет доступа? :-)

К сожалению нет.

-- 17.06.2017, 17:55 --

12d3
Реализовал, но падает на седьмом тесте :cry: Неверный ответ выдает.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>
#include <set>
#include <vector>

using namespace std;

class Block {
    long int rstart, rend, tstart, tend;
   
public:
    Block(long int time, long int start, long int end, long int duration) : rstart(start), rend(end), tstart(time), tend(time + duration - 1) {}
   
    Block() {}
   
    Block& operator=(const Block& rhs) {
        this->rstart = rhs.rstart;
        this->rend = rhs.rend;
       
        this->tstart = rhs.tstart;
        this->tend = rhs.tend;
       
        return *this;
    }
   
    bool operator<(const Block& rhs) const {
        return this->rstart < rhs.rstart;
    }
   
    friend ostream &operator<<(ostream &output, const Block &bl) {
        output << bl.tstart << " " << bl.rstart << " " << bl.rend << " " << bl.tend - bl.tstart + 1;
        return output;
    }
   
    bool resource_intersect(Block bl) const {
        return !(this->rstart > bl.rend || this->rend < bl.rstart);
    }
   
    bool time_intersect(Block bl) const {
        return !(this->tstart > bl.tend || this->tend < bl.tstart);
    }
};

set<Block>::iterator get_next(set<Block>::iterator it, set<Block> *blocked) {
    if (it == blocked->end()) {
        return it;
    }
    return next(it);
}

set<Block>::iterator get_prev(set<Block>::iterator it, set<Block> *blocked) {
    if (it == blocked->begin()) {
        return blocked->end();
    }
    return prev(it);
}

bool range_intersect(set<Block>::iterator low, set<Block>::iterator high, Block bl, set<Block> *blocked) {
    for (auto it = low; it != get_next(high, blocked); ++it) {
        if (it->time_intersect(bl) && it->resource_intersect(bl)) {
            return true;
        }
    }
    return false;
}

void clear_resource_range(set<Block>::iterator low, set<Block>::iterator high, Block bl, set<Block> *blocked) {
    vector<set<Block>::iterator> clear_me;
    for (auto it = low; it != get_next(high, blocked); ++it) {
        if (it->resource_intersect(bl)) {
            clear_me.push_back(it);
        }
    }
   
    for (auto it = clear_me.rbegin(); it != clear_me.rend(); ++it) {
        blocked->erase(*it);
    }
}

bool insert(set<Block> *blocked, Block bl) {
    if (!blocked->empty()) {
        set<Block>::iterator high = blocked->lower_bound(bl), low;
       
        if (high == blocked->end()) {
            --high;
        }
       
        low = high;
        for (auto it = high; it != blocked->end(); it = get_prev(it, blocked)) {
            if (*it < bl) {
                low = it;
                break;
            }
        }
       
        for (auto it = high; it != blocked->end(); it = get_next(it, blocked)) {
            if (bl < *it) {
                high = it;
                break;
            }
        }
       
        if (range_intersect(low, high, bl, blocked)) {
            return false;
        }
       
        clear_resource_range(low, high, bl, blocked);
    }
   
    blocked->insert(bl);
   
    return true;
}

int main() {
    long int n, m;
    cin >> n >> m;
    set<Block> blocked;
   
    for (long int i = 0; i < m; ++i) {
        long 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;
}
 


-- 17.06.2017, 18:10 --

12d3 в сообщении #1226243 писал(а):
На этапе проверки на пересечение с имеющимимся блокировками, ищем наименьший элемент, у которого start больше вставляемого, а также наибольший элемент, у которого start меньше вставляемого.

Кажется, я понял в чем дело. Для high надо искать тот элемент, у которого resource_start больше, чем resource_end вставляемого, а для low нужен наибольший элемент, у которого resource_start меньше, чем resource_start вставляемого. Сейчас попробую реализовать :mrgreen:

-- 17.06.2017, 18:18 --

Поменял
Код:
for (auto it = high; it != blocked->end(); it = get_next(it, blocked)) {
    if (bl < *it) {
        high = it;
        break;
    }
}

на
Код:
for (auto it = high; it != blocked->end(); it = get_next(it, blocked)) {
    if (!bl.resource_intersect(*it)) {
        high = it;
        break;
    }
}


Не помогло, все равно неверный ответ на 7 тесте... :|

-- 17.06.2017, 18:38 --

Убрал функцию clear_resource_range, поменял функцию range_intersect на
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
void erase(set<Block> *blocked, vector<set<Block>::iterator> items) {
    for (auto it = items.rbegin(); it != items.rend(); ++it) {
        blocked->erase(*it);
    }
}

bool range_intersect(set<Block>::iterator low, set<Block>::iterator high, Block bl, set<Block> *blocked) {
    vector<set<Block>::iterator> erase_us;
    for (auto it = low; it != get_next(high, blocked); ++it) {
        if (!it->time_intersect(bl)) {
            erase_us.push_back(it);
        } else if (it->resource_intersect(bl)) {
            erase(blocked, erase_us);
            return true;
        }
    }
    erase(blocked, erase_us);
    return false;
}
 

и мой код уже падает на 9-ом тесте :mrgreen:
Похоже, раньше он удалял какие-то активные блокировки...да и сейчас тоже...

 Профиль  
                  
 
 Re: Блокировки
Сообщение17.06.2017, 17:42 


04/05/13
125
Ура! Наконец-то дорешал :D :D :D Успешно прошел все 25 тестов:
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>
#include <set>
#include <vector>

using namespace std;

class Block {
    long int rstart, rend, tstart, tend;
   
public:
    Block(long int time, long int start, long int end, long int duration) : rstart(start), rend(end), tstart(time), tend(time + duration - 1) {}
   
    Block() {}
   
    Block& operator=(const Block& rhs) {
        this->rstart = rhs.rstart;
        this->rend = rhs.rend;
       
        this->tstart = rhs.tstart;
        this->tend = rhs.tend;
       
        return *this;
    }
   
    bool operator<(const Block& rhs) const {
        return this->rstart < rhs.rstart;
    }
   
    friend ostream &operator<<(ostream &output, const Block &bl) {
        output << bl.tstart << " " << bl.rstart << " " << bl.rend << " " << bl.tend - bl.tstart + 1;
        return output;
    }
   
    bool resource_intersect(Block bl) const {
        return !(this->rstart > bl.rend || this->rend < bl.rstart);
    }
   
    bool time_intersect(Block bl) const {
        return !(this->tstart > bl.tend || this->tend < bl.tstart);
    }
};

set<Block>::iterator get_next(set<Block>::iterator it, set<Block> *blocked) {
    if (it == blocked->end()) {
        return it;
    }
    return next(it);
}

set<Block>::iterator get_prev(set<Block>::iterator it, set<Block> *blocked) {
    if (it == blocked->begin()) {
        return blocked->end();
    }
    return prev(it);
}

void erase(set<Block> *blocked, vector<set<Block>::iterator> items) {
    for (auto it = items.rbegin(); it != items.rend(); ++it) {
        blocked->erase(*it);
    }
}

bool range_intersect(set<Block>::iterator low, set<Block>::iterator high, Block bl, set<Block> *blocked) {
    vector<set<Block>::iterator> erase_us;
    for (auto it = low; it != get_next(high, blocked); ++it) {
        if (!it->time_intersect(bl)) {
            erase_us.push_back(it);
        } else if (it->resource_intersect(bl)) {
            erase(blocked, erase_us);
            return true;
        }
    }
    erase(blocked, erase_us);
    return false;
}

bool insert(set<Block> *blocked, Block bl) {
    if (!blocked->empty()) {
        set<Block>::iterator high = blocked->upper_bound(bl), low;
       
        if (high == blocked->end()) {
            --high;
        }
       
        for (auto it = high; it != blocked->end(); it = get_prev(it, blocked)) {
            low = it;
            if (*it < bl) {
                break;
            }
        }
       
        for (auto it = high; it != blocked->end(); it = get_next(it, blocked)) {
            high = it;
            if (!it->resource_intersect(bl)) {
                break;
            }
        }
       
        if (range_intersect(low, high, bl, blocked)) {
            return false;
        }
    }
   
    blocked->insert(bl);
   
    return true;
}

int main() {
    long int n, m;
    cin >> n >> m;
    set<Block> blocked;
   
    for (long int i = 0; i < m; ++i) {
        long 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;
}
 


-- 17.06.2017, 19:47 --

12d3
Моя ошибка была что я не учитывал, что при поиске low величина resource_start блокировок могут равняться. А при поиске high забыл учесть, что resource_end вставляемой блокировки может задеть resource_start блокировок, следующих после выбранного high.

Всем большое спасибо :-)

-- 17.06.2017, 19:53 --

Geen в сообщении #1226414 писал(а):
Ну нельзя же так сразу... :mrgreen:

Теперь уже можно :-)

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


01/09/13
4318
inky в сообщении #1226577 писал(а):
Ура! Наконец-то дорешал :D :D :D Успешно прошел все 25 тестов

Поздравляю! :-)
inky в сообщении #1226577 писал(а):
Теперь уже можно

Тогда надо и такой вариант попробовать ;-)

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

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



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

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


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

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