644A - Parliament of Berland

Из условия задачи следует, что либо демократов и республиканцев поровну (если n чётно), либо демократов на одного больше (если n нечётно). Так как представители одной и той же партии не должны сидеть на соседних креслах, представим парламентский зал в виде шахматной доски, где левая верхняя клетка будет белой. Затем начнем перебирать ряды клеток сверху вниз, а клетки в каждом ряду слева направо и будем по очереди сажать парламентариев — демократов в белые клетки, а республиканцев в черные.

Таким образом, если n > a·b, ответом будет  - 1. В противном случае рассадка всегда найдется.

Для определения того, какого цвета клетка (и, соответственно, кого нужно в нее посадить), находящаяся в i-й строке и j-м столбце (в случае, если они нумеруются с единицы), можно поступить следующим образом. Если (i + j)mod2 = 0, значит соответствующая клетка должна быть белой, иначе чёрной.

cin >> n >> a >> b;
m  =  n - 1;
if (n > a * b) {
    cout << -1;
    return 0;
}
for (int i = 0; i < a; i++) {
    for (int j = 0; j < b; j++) {
        if ((i + j) % 2 == 0) {
            cout << n << " ";
            n  =  max(n - 2, 0);
        } else {
            cout << m << " ";
            m  =  max(m - 2, 0);
        }
    }
    cout << endl;
}

644B - Processing Queries

Для решения данной задачи очень удобно воспользоваться структурой данных, которая называется очередь.

Очередь — это структура данных со следующим принципом доступа к элементам: «первый пришёл — первый ушёл». Добавление элемента (\textit{push}) возможно лишь в конец очереди, а взять элемент из очереди можно только из её начала (\textit{front}). Удалить элемент можно также только из начала очереди (\textit{pop}).

В данной задаче нужно было перебрать все запросы в хронологическом порядке. Будем хранить в очереди времена окончания обработки запросов. Для текущего запроса, пока в начале очереди находятся запросы, которые закончат обрабатываться не позднее, чем появился текущий запрос, нужно просто удалять их из начала очереди, так как они никак не повлияют на текущий. Если после этих действий размер очереди равен максимальному допустимому числу, ответ для текущего запроса  - 1. В противном случае, нужно добавить время окончания обработки текущего запроса в очередь, вывести это время и продолжить алгоритм.

queue<long long> q;
int main() {
	cin >> n >> b;
	for (int i = 0; i < n; i++) 	{
		cin >> t >> d;
		while (q.size() && q.front() <= t)
			q.pop();
		if (q.empty()) 
			ans = t;
		if (q.size() <= b)  {
			ans += d;
                        q.push(ans);
                        cout << ans << ' ';
               } else
		cout << -1 << ' ';
	}
}

644C - Hostname Aliases