Решение задачи Социальная сеть (сложная версия) с Codeforces

Без пояснения   Просмотров: 41


Единственное отличие между простой и сложной версиями — ограничения на n и k.

Вы общаетесь в одной из популярных социальных сетей, используя свой смартфон. Ваш смартфон может показывать не более k самых недавних бесед с вашими друзьями. Изначально экран смартфона пуст (то есть количество показанных бесед равно 0).

Каждая беседа — это ваш диалог с каким-то из ваших друзей. Всего существует не более одной беседы с каждым из ваших друзей. Таким образом, каждая беседа однозначно определяется вашим другом.

Вы (внезапно!) обладаете возможностью видеть будущее. Вы знаете, что в течение дня вы получите n сообщений, i-е сообщение будет получено от друга с ID idi (1≤idi≤109).

Если вы получаете сообщение от друга idi тогда, когда беседа с ним сейчас показана на экране смартфона, то ничего не происходит: беседы на экране не меняются и не меняют свой относительный порядок, вы просто читаете сообщение и продолжаете ждать новых сообщений.

Иначе (то есть тогда, когда на экране нет беседы с другом idi):

Сначала, если количество бесед, отображенных на экране, равно k, последняя беседа (которая имеет позицию k) удаляется с экрана.
Теперь количество бесед на экране гарантированно меньше k и беседа с другом idi не отображена на экране.
Беседа с другом idi появляется на первой (верхней) позиции на экране и все другие отображенные беседы сдвигаются на одну позицию вниз.
Ваша задача — найти список бесед (в порядке, в котором они будут отображены на экране) после обработки всех n сообщений.

Код

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n, k;
	cin >> n >> k;
	deque<int> q;
	set<int> s;
	for(int i = 0, x;i < n;i++){
		cin >> x;
		if(s.find(x) != s.end()) continue;
		if(q.size() == k)
			s.erase(q.back()), q.pop_back();
		q.push_front(x);
		s.insert(x);
	}
	cout << q.size() << "\n";
	for(auto u : q)
		cout << u << " ";
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться