2014 dxdy logo

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

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




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


04/05/13
125
Есть $n$ абстрактных ресурсов, пронумерованные целыми числами от $1$ до $n$. Каждый ресурс в конкретный момент времени может находиться либо в занятом, либо в свободном состоянии. Изначально (в момент времени $0$) все ресурсы находятся в свободном состоянии.
Блокировка с порядковым номером $i$ представляет из себя четверку чисел ($s_i, l_i, r_i, d_i$), обозначающих соответственно время старта ($s_i \geqslant 1$), левую и правую границы индексов ресурсов ($1 \leqslant l_i \leqslant r_i \leqslant n$), продолжительность ($d_i \geqslant 1$) блокировки.
Блокировка $i$ называется принятой, если на момент времени $s_i$ все ресурсы с индексами в диапазоне $[l_i, r_i]$ находятся в свободном состоянии. Принятая блокировка $i$ переводит все ресурсы с индексами в диапазоне $[l_i, r_i]$ в занятое состояние для всех моментов времени в диапазоне $[s_i, s_i + d_i)$.
Необходимо реализовать алгоритм, реализующий данную логику.

Формат входных данных
В первой строке входных данных записано два числа — $n, m$ $(1 \leqslant n, m \leqslant 100000)$, разделенных одним пробелом.
В последующих $m$ строках задано описание блокировок в примере Васи. В $i$-й из этих строк записано четыре числа — $s_i, l_i, r_i, d_i$ $(1 \leqslant s_i \leqslant 10^9, 1 \leqslant l_i \leqslant r_i \leqslant 10^9, 1 \leqslant d_i \leqslant 10^9)$, разделенных одним пробелом.
Гарантируется, что все $s_i$ различны.Блокировки следуют в порядке возрастания величины $s_i$.

Формат выходных данных
В $i$-й строке выходных данных необходимо вывести результат обработки $i$-й блокировки в порядке следования во входных данных: если $i$-я блокировка является принятой, вывести Yes, иначе No.


Мое решение:
Код:
#include <iostream>
#include <vector>

using namespace std;

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

int clear (int time, vector<block> *blocked) { // clear outdated blocks
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            blocked->erase(it);
            return 1;
        }
    }
    return 0;
}

int intersects(vector<block>::const_iterator it, int start, int end) {
    if ((start <= it->start && it->start <= end) ||
        (start <= it->end   && it->end   <= end)) {
        return 1;
    }
    return 0;
}

int block_me(vector<block> *blocked, int time, int start, int end, int duration) {
    while (clear(time, blocked) == 1);
   
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (intersects(it, start, end) == 1) {
            cout << "No";
            return 1;
        }
    }
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->push_back(t);
    cout << "Yes";
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<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;
}


Решение проверяется системой yandex contest. На седьмом тесте мой код выдает неверный ответ. Никак не могу понять, что я упустил?

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


06/07/11
5604
кран.набрать.грамота
Я вряд ли помогу вам именно с С/С++, но из общих соображений:
1. На каких входных данных вы тестировали код?
2.
inky в сообщении #1226004 писал(а):
На седьмом тесте мой код выдает неверный ответ.
Как мне кажется, было бы неплохо уточнить, что такое "седьмой тест".

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


04/05/13
125
rockclimber
Седьмой тест -- это седьмой тест автоматической системы тестирования яндекса. К сожалению, у меня нет доступа к этим тестам :cry:

-- 16.06.2017, 13:15 --

У меня был еще другой вариант решения, но он на 19-ом тесте слишком долго работал, не прошел ограничение по времени.
Вот он:
Код:
#include <iostream>

using namespace std;

int block_me(int *a, int time, int start, int end, int duration) {
    for (int i = start; i <= end; ++i) {
        if (a[i] > time) {
            printf("No");
            for (int j = start; j < i; ++j) {
                a[j] = time;
            }
            return 1;
        }
        a[i] = time + duration;
    }
    printf("Yes");
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    int resources[n];
    for (int i = 0; i < n; ++i) {
        resources[i] = 0;
    }
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        block_me(resources, s, l - 1, r - 1, d);
        printf("\n");
    }
   
    return 0;
}

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


01/09/13
3013
inky в сообщении #1226004 писал(а):
Никак не могу понять, что я упустил?

А перекрытие блоков как считается?

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


04/05/13
125
Geen
Перекрытие я учитываю в этой функции:
Код:
int intersects(vector<block>::const_iterator it, int start, int end) {
    if ((start <= it->start && it->start <= end) ||
        (start <= it->end   && it->end   <= end)) {
        return 1;
    }
    return 0;
}

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


01/09/13
3013
rockclimber в сообщении #1226007 писал(а):
Как мне кажется, было бы неплохо уточнить, что такое "седьмой тест".

Я думаю, что это просто очередной набор данных для тестирования.

-- 16.06.2017, 11:25 --

inky в сообщении #1226033 писал(а):
Перекрытие я учитываю в этой функции:

Так я спрашивал "как" ;-)

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


04/05/13
125
Geen
Вначале понял это как "пересечение". Я лишь смотрел на пересечения. Если новая блокировка пересекается с одной из активных блокировок -- значит блокировку надо отменять.

-- 16.06.2017, 13:31 --

А учитываю я их так: если начало либо конец новой блокировки лежит внутри активной блокировки, то они пересекаются.

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


01/09/13
3013
inky в сообщении #1226035 писал(а):
А учитываю я их так: если начало либо конец новой блокировки лежит внутри активной блокировки, то они пересекаются.

Лучше бы зайти с другого конца - когда блокировки не пересекаются?

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


06/07/11
5604
кран.набрать.грамота
Так у вас два измерения - ресурс и время, то есть вы должны искать пересечения прямоугольников. Ваш код не похож на поиск пересечения прямоугольников...

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


04/05/13
125
rockclimber в сообщении #1226040 писал(а):
Так у вас два измерения - ресурс и время, то есть вы должны искать пересечения прямоугольников. Ваш код не похож на поиск пересечения прямоугольников...

Время я специально отсекаю в функции $clear$. Чтобы не мучиться с двумя измерениями :-)

-- 16.06.2017, 13:40 --

Geen
Сейчас попробую.

-- 16.06.2017, 13:45 --

Geen
Спасибо, работало :D
Поменял функцию $intersects$:
Код:
int intersects(vector<block>::const_iterator it, int start, int end) {
    if ((it->start < start && it->end < start) ||
        (it->start > end && it->end > end)) {
        return 0;
    }
    return 1;
}

Видимо, старая неверно считала пересечение :facepalm:

Но теперь я не укладываюсь по времени на 17-ом тесте...

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


06/07/11
5604
кран.набрать.грамота
Меня вот что смущает:
inky в сообщении #1226004 писал(а):
Гарантируется, что все $s_i$ различны. Блокировки следуют в порядке возрастания величины $s_i$.
Но не гарантируется, что $s_{i+1} > s_i + d_i$
Может, в этом проблема?

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


04/05/13
125
rockclimber в сообщении #1226048 писал(а):
Но не гарантируется, что $s_{i+1} > s_i + d_i$
Может, в этом проблема?

Нет, тут все в порядке. Если $s_{i} < s_k + d_k$, то надо блокировка считается непринятой.

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


01/09/13
3013
inky в сообщении #1226029 писал(а):
У меня был еще другой вариант решения, но он на 19-ом тесте слишком долго работал, не прошел ограничение по времени.

Похоже в яндексе знают толк в извращениях :mrgreen:
Но Ваш текущий вариант мне как-то тоже не сильно нравится - слишком много удалений из начала массива (вектора) может случиться...

-- 16.06.2017, 11:52 --

inky в сообщении #1226043 писал(а):
Но теперь я не укладываюсь по времени на 17-ом тесте...

Видимо оно и случилось...

-- 16.06.2017, 11:53 --

inky в сообщении #1226043 писал(а):
Поменял функцию $intersects$:

Избыточные условия....

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


04/05/13
125
Geen в сообщении #1226055 писал(а):
Но Ваш текущий вариант мне как-то тоже не сильно нравится - слишком много удалений из начала массива (вектора) может случиться...

Только что попробовал перенести эти удаления поближе - в саму функцию block_me:
Код:
#include <iostream>
#include <vector>

using namespace std;

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

int intersects(vector<block>::const_iterator it, int start, int end) {
    if ((it->start < start && it->end < start) ||
        (it->start > end && it->end > end)) {
        return 0;
    }
    return 1;
}

int block_me(vector<block> *blocked, int time, int start, int end, int duration) {
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            blocked->erase(it);
            return block_me(blocked, time, start, end, duration);
        }
        if (intersects(it, start, end) == 1) {
            cout << "No";
            return 1;
        }
    }
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->push_back(t);
    cout << "Yes";
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<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;
}


Но толку не было. Совсем :)

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


06/07/11
5604
кран.набрать.грамота
А можете вкратце словами описать алгоритм? Я не уверен, что правильно понял код. И, как я понимаю, у вас остались только проблемы с производительностью?

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

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



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

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


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

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