Задача про деки

@Rasul96 · Регистрация: 04.04.2013

Author24 — интернет-сервис помощи студентам

Попалась такая вот задача на e-olimp:

Деки на 6 мегабайтах
Напишите программу, которая умеет оперировать с большим количеством деков. Дек - это "очередь с двумя концами".
Входные данные

Первая строка содержит общее количество команд n (0 ≤ n ≤ 150000). Каждая из следующих n строк содержит описание команды:

"pushfront A B" - вставить число B в начало дека A;
"pushback A B" - вставить число B в конец дека A;
"popfront A" - удалить первый элемент дека A;
"popback A" - удалить последний элемент дека A.
Для каждой команды параметры A и B - целые числа от 1 до 150000 включительно.

Выходные данные

Для каждой команды popfront или popback выведите удаляемое число. Гарантируется, что перед выполнением команды удаления соответствующий дек не пуст.

Мой код:

C++ (Qt)

#include <iostream>
#include <deque>
#include <string>
#include <map>
using namespace std;
 
int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   map <int, deque <int> > a;
   int n, k, t;
   string s;
   cin >> n;
   while (n--) {
       cin >> s;
       if (s == "pushfront") {
           cin >> k >> t;
           a[k].push_front(t);
       }
       else if (s == "pushback") {
           cin >> k >> t;
           a[k].push_back(t);
       }
       else if (s == "popfront") {
           cin >> k;
           cout << a[k].front() << endl;
           a[k].pop_front();
       }
       else {
           cin >> k;
           cout << a[k].back() << endl;
           a[k].pop_back();
       }
   }
}

Я не могу вместить программу в 6 мегабайтов. Что делать подскажите. Заранее благодарю!

@salam · 16.03.2015, 19:09

храни обычный статический массив из 150000 деков. должно влезть.

@Rasul96 · 16.03.2015, 20:22 **[ТС]**

salam, Да нет, так еще хуже!

@wingblack · 17.03.2015, 10:44

Если ручками реализовать деки через указатели, то получим
4 * 2 = 8 байт на дек (по 4 байта на 2 указателя в 32-битной системе)
8 * 150 000 = 1 200 000 байт на массив деков
4 * 2 + 4 = 12 байт на число
12 * 150 000 = 1 800 000 на все числа
итого 3 000 000 байт сильно меньше 6 Мб

В 64-битной системе уже не все так радужно, указатели по 8 байт, значит 16 байт на дек, 16+4=20 на числа, итого
(16+20)*150000 = 5 400 000 байт

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	16.03.2015, 19:09	2
	храни обычный статический массив из 150000 деков. должно влезть. 0

@Rasul96 27 / 27 / 6 Регистрация: 04.04.2013 Сообщений: 137 Записей в блоге: 1
	16.03.2015, 20:22 [ТС]	3
	salam, Да нет, так еще хуже! 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,037
	17.03.2015, 10:44	4
	Сообщение было отмечено Rasul96 как решение Решение Если ручками реализовать деки через указатели, то получим 4 * 2 = 8 байт на дек (по 4 байта на 2 указателя в 32-битной системе) 8 * 150 000 = 1 200 000 байт на массив деков 4 * 2 + 4 = 12 байт на число 12 * 150 000 = 1 800 000 на все числа итого 3 000 000 байт сильно меньше 6 Мб В 64-битной системе уже не все так радужно, указатели по 8 байт, значит 16 байт на дек, 16+4=20 на числа, итого (16+20)*150000 = 5 400 000 байт 1

Задача про деки

Решение