Поиск кратчайшего пути в графе

Дан неориентированный граф, длины ребер в котором равны 0 или 1. Необходимо найти длину кратчайшего пути из вершины A в вершину B.
В первой строке входа задано 4 целых числа n, m, a, b количество вершин и ребер графа, номер вершины A и номер вершины B соответственно. Вершины пронумерованы от 1 до n. 1 ≤ m, n ≤ 100 000, 1 ≤ a, b ≤ n. В каждой из следующих m строк по три целых числа, первое из которых означает номер начальной вершины ребра, второе номер конечной вершины ребра, третье длину ребра (0 или 1).
Выведите длину кратчайшего пути из вершины A в вершину B . Если пути из A в B не существует, выведите -1.

#include <stdio.h>
#include <vector>
#include <algorithm>

using std::vector;
using std::swap;

const int kMaxDistance = 1000000;

struct NodeLengthPair {
  int node_;
  int length_;

  NodeLengthPair(int node, int length):
    node_(node), length_(length) {}
};

struct DistancePositionPair {
  int distance_;
  int heap_position_;
  DistancePositionPair(int distance, int heap_position):
    distance_(distance), heap_position_(heap_position) {}
};

void ReadInput(vector< vector<NodeLengthPair> >& graph_edges,
               int& source_node,
               int& destination_node) {
  int nodes_num, edges_num, source, destination;
  scanf("%d %d %d %d", &nodes_num, &edges_num, &source, &destination);
  graph_edges.resize(nodes_num);
  source_node = source - 1;
  destination_node = destination - 1;
  int node_from, node_to, length;
  for (int counter = 0; counter < edges_num; ++counter) {
    scanf("%d %d %d", &node_from, &node_to, &length);
    graph_edges[node_from - 1].push_back(NodeLengthPair(node_to - 1, length));
    graph_edges[node_to - 1].push_back(NodeLengthPair(node_from - 1, length));
  }
}

void Heapify(int root_index,
             vector<int>& nodes_heap,
             vector<DistancePositionPair>& distance) {
  int left_son_index, right_son_index, smallest_index;
  left_son_index = 2 * root_index + 1;
  right_son_index = 2 * root_index + 2;
  smallest_index = root_index;
  if (left_son_index < nodes_heap.size() &&
      distance[nodes_heap[left_son_index]].distance_ <
          distance[nodes_heap[smallest_index]].distance_) {
    smallest_index = left_son_index;
  }
  if (right_son_index < nodes_heap.size() &&
      distance[nodes_heap[right_son_index]].distance_ <
          distance[nodes_heap[smallest_index]].distance_) {
    smallest_index = right_son_index;
  }
  if (smallest_index != root_index) {
    swap(distance[nodes_heap[root_index]].heap_position_,
         distance[nodes_heap[smallest_index]].heap_position_);
    swap(nodes_heap[root_index], nodes_heap[smallest_index]);
    Heapify(smallest_index, nodes_heap, distance);
  }
}

void MakeHeap(vector<int>& nodes_heap,
              vector<DistancePositionPair>& distance) {
  for (int counter = nodes_heap.size() / 2; counter >= 0; --counter) {
    Heapify(counter, nodes_heap, distance);
  }
}

int ExtractMin(vector<int>& nodes_heap,
               vector<DistancePositionPair>& distance) {
  int min = nodes_heap.front();
  nodes_heap.front() = nodes_heap.back();
  nodes_heap.pop_back();
  distance[nodes_heap.front()].heap_position_ = 0;
  Heapify(0, nodes_heap, distance);
  return min;
}

void ShiftUp(int index,
            vector<int>& nodes_heap,
            vector<DistancePositionPair>& distance) {
  if (index == 0) {
    return;
  }
  int parent_index = index % 2 == 0 ? (index - 2) / 2 : index / 2;
  if (distance[nodes_heap[parent_index]].distance_ >
          distance[nodes_heap[index]].distance_) {
    swap(distance[nodes_heap[parent_index]].heap_position_,
         distance[nodes_heap[index]].heap_position_);
    swap(nodes_heap[parent_index], nodes_heap[index]);
    ShiftUp(parent_index, nodes_heap, distance);
  }
}

int FindMinPath(const vector< vector<NodeLengthPair> >& graph_edges,
              int source_node,
              int destination_node) {
  vector<DistancePositionPair> distance(graph_edges.size(),
      DistancePositionPair(kMaxDistance, 0));
  distance[source_node].distance_ = 0;
  vector<int> nodes_heap(graph_edges.size());
  for (int counter = 0; counter < nodes_heap.size(); ++counter) {
    nodes_heap[counter] = counter;
    distance[counter].heap_position_ =  counter;
  }
  MakeHeap(nodes_heap, distance);
  int current_node;
  while (!nodes_heap.empty()) {
    current_node = ExtractMin(nodes_heap, distance);
    if (current_node == destination_node) {
      break;
    }
    for (vector<NodeLengthPair>::const_iterator adjanced_it =
             graph_edges[current_node].begin();
         adjanced_it != graph_edges[current_node].end();
         ++adjanced_it) {
      if (distance[adjanced_it->node_].distance_ >
              distance[current_node].distance_ + adjanced_it->length_) {
        distance[adjanced_it->node_].distance_ =
            distance[current_node].distance_ + adjanced_it->length_;
        ShiftUp(distance[adjanced_it->node_].heap_position_,
                nodes_heap,
                distance);
      }
    }
  }
  return distance[destination_node].distance_ == kMaxDistance ?
        -1 : distance[destination_node].distance_;
}

int main() {
  vector< vector<NodeLengthPair> > graph_edges;
  int source_node, destination_node;
  ReadInput(graph_edges, source_node, destination_node);
  printf("%d\n", FindMinPath(graph_edges, source_node, destination_node));
  return 0;
}

Поиск моста в неориентированном графе

Хонти хочет начать войну против Пандеи. План Хонти состоит в том, чтобы используя эффект неожиданности навести ужас на пандейцев, создать хаос, и в этих условиях быстро завоевать страну. Чтобы успешно воплотить этот план в жизнь, хонтийцам необходимо провести первую, самую важную операцию.
Цель операции разделить Пандею на две несвязанные части, разрушив всего лишь
одну дорогу (изначально карта Пандеи представляет собой связный граф). Хонтийская разведка уже добыла карты Пандеи, передала их экспертам, которые провели исследование и выяснили стоимость разрушения каждой из дорог страны-противника. Вам передали карту всех дорог вместе со стоимостями их разрушения. Вам нужно выбрать самую дешевую дорогу, удовлетворяющую запросам хонтийцев: предстоящая война еще потребует значительных ресурсов.
В первой строке входа заданы два целых числа n и m количество городов и количество дорог Пандеи соответственно. Дороги в Пандее двусторонние. В каждой из следующих m строк по три числа a, b и c номера начального и конечного горо дов дороги (города нумеруются с единицы) и стоимость разрушения данной дороги. 1 ≤ m, n ≤ 50 000. 1 ≤ a, b ≤ n. a = b. 1 ≤ c ≤ 1 000 000 000.
Выведите единственное число наименьшую стоимость дороги, которую можно разрушить, чтобы нарушить связность Пандеи. Если таких дорог не существует, выведите -1.

Проводится поиск в ширину, чтобы найти так называемые "мосты" - ребра, удаление которых, делает граф несвязным. Затем выбирается тот мост, разрушение которого самое дешевое.

#include<stdio.h>
#include<stack>
#include<vector>
#include<algorithm>

struct NodeCostPair {
  int node_;
  int cost_;

  NodeCostPair(int node, int cost):
    node_(node), cost_(cost) {}
};

struct ReturnInfo {
  int current_node_;
  int prev_node_;
  std::vector<NodeCostPair>::const_iterator node_it_;

  ReturnInfo(int current_node,
             int prev_node,
             std::vector<NodeCostPair>::const_iterator node_it):
    current_node_(current_node), prev_node_(prev_node), node_it_(node_it) {}
};

struct Edge {
  int node_from_;
  int node_to_;
  int cost_;

  Edge(int node_from, int node_to, int cost):
    node_from_(node_from), node_to_(node_to), cost_(cost) {}
};

enum Colors {
  WHITE = 0,
  GRAY = 1,
  BLACK = 2
};

template <typename T>
const T& min3(const T& a, const T& b, const T& c) {
  return std::min(a, std::min(b, c));
}

const int kMaxNodesNumber = 100000;

void DFS(const std::vector< std::vector<NodeCostPair> >& graph_edges,
         std::vector<int>& times_in,
         std::vector<int>& min_enter_time,
         std::vector<Edge>& dfs_edges) {
  std::stack<ReturnInfo> stack_nodes;
  std::vector<char> colors(graph_edges.size(), 0);
  int current_node = 0;  // Begin from the node 0.
  int prev_node = -1;
  int timer = 0;
  times_in.resize(graph_edges.size(), kMaxNodesNumber);
  times_in[0] = timer;
  min_enter_time.resize(graph_edges.size(), kMaxNodesNumber);
  bool go_deeper;
  bool exist_not_visited_nodes = true;
  std::vector<NodeCostPair>::const_iterator node_next_to_visit =
      graph_edges[current_node].begin();
  while (exist_not_visited_nodes) {
    colors[current_node] = GRAY;
    go_deeper = false;
    for (/* Loop initialization not needed. */;
         node_next_to_visit != graph_edges[current_node].end();
         ++node_next_to_visit) {
      if (node_next_to_visit->node_ != prev_node &&
          colors[node_next_to_visit->node_] == GRAY) {
        // Back edge.
        min_enter_time[current_node]
            = min3(times_in[node_next_to_visit->node_],
                   times_in[current_node],
                   min_enter_time[current_node]);
      }
      if (colors[node_next_to_visit->node_] == BLACK) {
        // Tree edge.
        min_enter_time[current_node]
            = min3(min_enter_time[node_next_to_visit->node_],
                   min_enter_time[current_node],
                   times_in[current_node]);
      }
      if (colors[node_next_to_visit->node_] == WHITE) {
        dfs_edges.push_back(Edge(current_node,
                                 node_next_to_visit->node_,
                                 node_next_to_visit->cost_));
        stack_nodes.push(ReturnInfo(current_node,
                                    prev_node,
                                    node_next_to_visit));
        prev_node = current_node;
        current_node = node_next_to_visit->node_;
        node_next_to_visit = graph_edges[current_node].begin();
        ++timer;
        times_in[current_node] = min_enter_time[current_node] = timer;
        go_deeper = true;
        break;
      }
    }
    if (!go_deeper) {
      colors[current_node] = BLACK;
      if (stack_nodes.empty()) {
        exist_not_visited_nodes = false;
      } else {
        // Return to the previous node
        current_node = stack_nodes.top().current_node_;
        prev_node = stack_nodes.top().prev_node_;
        node_next_to_visit = stack_nodes.top().node_it_;
        stack_nodes.pop();
      }
    }
  }
}

void ReadGraphEdges(std::vector< std::vector<NodeCostPair> >& graph_edges) {
  int nodes_num, edges_num;
  scanf("%d %d", &nodes_num, &edges_num);
  graph_edges.resize(nodes_num);
  int node_from, node_to, cost;
  for (int counter = 0; counter < edges_num; ++counter) {
    scanf("%d %d %d", &node_from, &node_to, &cost);
    graph_edges[node_from - 1].push_back(NodeCostPair(node_to - 1, cost));
    graph_edges[node_to - 1].push_back(NodeCostPair(node_from - 1, cost));
  }
}

const int kMinCost = -1;

int FindMinBridgeCost(const
                      std::vector< std::vector<NodeCostPair> >& graph_edges) {
  int min_cost = kMinCost;
  std::vector<int> times_in;
  std::vector<int> min_enter_time;
  std::vector<Edge> dfs_edges;
  DFS(graph_edges, times_in, min_enter_time, dfs_edges);
  for (std::vector<Edge>::const_iterator edge_it = dfs_edges.begin();
       edge_it != dfs_edges.end(); ++edge_it) {
    if (min_enter_time[edge_it->node_to_] > times_in[edge_it->node_from_]) {
      if (min_cost == -1) {
        min_cost = edge_it->cost_;
      } else {
        min_cost = std::min(min_cost, edge_it->cost_);
      }
    }
  }
  return min_cost;
}

int main() { 
  std::vector< std::vector<NodeCostPair> > graph_edges;
  ReadGraphEdges(graph_edges);
  printf("%d\n", FindMinBridgeCost(graph_edges));
  return 0;
}

Z-функция

Дана строка s. Нужно вычислить Z-функцию s - для каждого i от 1 до |s|.

Z[i]=max{j: 0 <= j <= |s| - i + 1, s[1..j] = s[i..i + j -1]}.

В единственной строке входа - строка s длиной не более 1 000 000 символов, состоящая из маленьких латинских букв.
В выходной файл выводится для каждого i от 1 до |s| число Z[i]. Числа разделены пробелами.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::max;

inline int LongestCommonPrefix(const string& input_string,
                       int first_start,
                       int second_start) {
  int index = 0;
  while (max(first_start + index, second_start + index) < input_string.size() &&
         input_string[first_start + index] ==
           input_string[second_start + index]) {
    ++index;
  }
  return index;
}

void ZFunction(const string& input_string, vector<int>& result_values) {
  result_values.resize(input_string.size());
  result_values[0] = input_string.size();
  int left_index = 0;
  int right_index = 0;
  int index;
  for (int current_index = 1; current_index < input_string.size();
       ++current_index) {
    if (current_index > right_index) {
      index = LongestCommonPrefix(input_string, 0, current_index);
      result_values[current_index] = index;
      left_index = current_index;
      right_index = current_index + index - 1;
    } else if (result_values[current_index - left_index] <
               right_index - current_index + 1) {
      result_values[current_index] = result_values[current_index - left_index];
    } else {
      index = LongestCommonPrefix(input_string, right_index + 1,
                                 right_index - current_index + 1) + 1;
      result_values[current_index] = right_index - current_index + index;
      left_index = current_index;
      right_index = right_index + index - 1;
    }
  }
}

void WriteOutput(const vector<int>& vec) {
  for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

int main() {
  string input_string;
  vector<int> z_function_values;
  cin >> input_string;
  ZFunction(input_string, z_function_values);
  WriteOutput(z_function_values);
  return 0;
}

Простейший SMTP клиент.

Принимает ip-адрес smtp сервера, как первый и единственный аргумент, проводит элементарную сессию из сообщений "HELO", затем "QUIT", пишет всю переписку в stdout.

#include <arpa/inet.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <unistd.h>
#include <string.h>
#include <cerrno>
#include <cstdlib>
#include <cstdio>

const int port_number = 25;

void ReadFromSocket(int socket_descriptor, char *server_answer, int len) {
  int num_bytes = read(socket_descriptor, server_answer, len);
  if (num_bytes < 0) {
    perror("ERROR reading socket");
    exit(EXIT_FAILURE);
  }
}

void WriteToSocket(int socket_descriptor, const char *msg, int len) {
  int num_bytes = write(socket_descriptor, msg, len);
  if (num_bytes < 0) {
    perror("ERROR writing socket");
    exit(EXIT_FAILURE);
  }
}

void SimpleSMTPSession(int socket_descriptor) {
  char buffer[256];
  ReadFromSocket(socket_descriptor, buffer, 255);
  printf("Server: %s", buffer);

  strcpy(buffer, "HELO CLIENT\n");
  WriteToSocket(socket_descriptor, buffer, strlen(buffer));
  printf("Client: %s", buffer);

  ReadFromSocket(socket_descriptor, buffer, 255);
  printf("Server: %s", buffer);

  strcpy(buffer, "QUIT\n");
  WriteToSocket(socket_descriptor, buffer, strlen(buffer));
  printf("Client: %s", buffer);

  ReadFromSocket(socket_descriptor, buffer, 255);
  printf("Server: %s", buffer);
}

void EstablishConnection(int *socket_descriptor, char *address) {
  *socket_descriptor = socket(AF_INET, SOCK_STREAM, 0);
  if (*socket_descriptor < 0) {
    perror("ERROR opening socket");
    exit(EXIT_FAILURE);
  }

  struct sockaddr_in server_address;
  memset(&server_address, 0, sizeof(server_address));
  server_address.sin_family = AF_INET;
  int pton_result = inet_pton(AF_INET, address, &(server_address.sin_addr));
  if (pton_result == 0) {
    printf("ERROR argument is not IP address\n");
    exit(EXIT_FAILURE);
  }
  if (pton_result < 0) {
    perror("ERROR argument is not valid IP address");
    exit(EXIT_FAILURE);
  }
  server_address.sin_port = htons(port_number);

  if (connect(*socket_descriptor,
              (struct sockaddr*)&server_address, sizeof(server_address)) < 0) {
    perror("ERROR connecting");
    exit(EXIT_FAILURE);
  }
}

void CloseConnection(int socket_descriptor) {
  if (close(socket_descriptor) < 0) {
    perror("ERROR socket closing");
    exit(EXIT_FAILURE);
  }
}

int main(int argc, char **argv) {
  if (argc != 2) {
    printf("Not enough arguments!\nUsage: %s ip_address\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  int socket_descriptor;
  EstablishConnection(&socket_descriptor, argv[1]);

  SimpleSMTPSession(socket_descriptor);

  CloseConnection(socket_descriptor);

  return 0;
}

Цитата

Ja! Diesem Sinne bin ich ganz ergeben,
Das ist der Weisheit letzter Schluss:
Nur der verdient sich Freiheit wie das Leben,
Der täglich sie erobern muss.

... Жизни годы
Прошли не даром; ясен предо мной
Конечный вывод мудрости земной:
Лишь тот достоин жизни и свободы,
Кто каждый день за них идёт на бой!

Скачать все ссылки со страницы.

# for i in `lynx --dump $url | awk '/http/{print $2}'`; do wget $i; done

Модель аллокатора с использованием кучи и двусвязного списка

В распоряжении у менеджера памяти находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера - обрабатывать запросы приложений на выделение и освобождение памяти. Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом наш менеджер выделяет память из самого длинного свободного блока, а если таких несколько, то из них он выбирает тот, у которого номер первой ячейки - наименьший. После этого выделенный ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется. Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T - запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется. Требуется написать симуляцию менеджера памяти, удовлетворяющую приведенным критериям.
Количество ячеек 1<=N<=2^(31)-1, количество запросов 1<=m<=10^5. На вход подаются числа N и M, а затем M чисел, если число положительное - выделение памяти, отрицательное - освобождение. Для каждого запроса на выделение памяти в выход выводится одно число на отдельной строке с результатом выполнения запроса. Если память была выделена, выводится номер первой ячейки памяти в выделенном блоке, иначе выводится -1.
Для хранения свободных отрезков используется куча с итераторами на отрезки из двусвязного списка, в котором хранятся все отрезки. Приведенное решение имеет асимптотику O(m log(m)).

#include <vector>
#include <list>
#include <algorithm>
#include <cstdio>

using std::vector;
using std::list;
using std::swap;

struct Chunk {
  int start_;
  int length_;
  bool is_free_;
  int index_;

  Chunk(int start = 0, int length = 0, bool is_free = false, int index = 0):
      start_(start), length_(length), is_free_(is_free), index_(index) {}

  bool operator <(const Chunk& other) const {
    if (length_ < other.length_) {
      return true;
    }
    if (length_ == other.length_) {
      return start_ > other.start_;
    }
    return false;
  }

  bool operator ==(const Chunk& other) const {
    return start_ == other.start_ && length_ == other.length_ &&
        is_free_ == other.is_free_ && index_ == other.index_;
  }

  bool operator >(const Chunk& other) const {
    return other < *this;
  }
};

class MaxChunkHeap {
private:
  vector<list<Chunk>::iterator> array;
public:
  bool empty() const {
    return array.empty();
  }

  void Heapify(int root_index) {
    int left_son_index, right_son_index, largest_index;
    left_son_index = 2 * root_index + 1;
    right_son_index = 2 * root_index + 2;
    largest_index = root_index;
    if (left_son_index < array.size() &&
        *(array[left_son_index]) > *(array[largest_index])) {
      largest_index = left_son_index;
    }
    if (right_son_index < array.size() &&
        *(array[right_son_index]) > *(array[largest_index])) {
      largest_index = right_son_index;
    }
    if (largest_index != root_index) {
      swap(array[root_index]->index_, array[largest_index]->index_);
      swap(array[root_index], array[largest_index]);
      Heapify(largest_index);
    }
  }

  void ChangeKey(int index, list<Chunk>::iterator new_key) {
    array[index] = new_key;
    new_key->index_ = index;
    Heapify(index);
    while (index > 0 && *(array[(index - 1) / 2]) < *(array[index])) {
      swap(array[(index - 1) / 2]->index_, array[index]->index_);
      swap(array[(index - 1) / 2], array[index]);
      index = (index - 1) / 2;
    }
  }

  void Insert(list<Chunk>::iterator new_key) {
    array.push_back(new_key);
    ChangeKey(array.size() - 1, new_key);
  }

  list<Chunk>::iterator GetMax() {
    return array[0];
  }

  list<Chunk>::iterator ExtractMax() {
    list<Chunk>::iterator max_element = array[0];
    array[0] = array[array.size() - 1];
    array[0]->index_ = 0;
    array.pop_back();
    Heapify(0);
    return max_element;
  }

  void Remove(int index) {
    if (array.empty())
      return;
    array[index] = array[array.size() - 1];
    array[index]->index_ = index;
    array.pop_back();
    ChangeKey(index, array[index]);
  }

  MaxChunkHeap() {}
};

class Allocator {
private:
  MaxChunkHeap memory_heap_;
  list<Chunk> chunks_list_;
  vector<list<Chunk>::iterator> allocated_chunks_;
  int operations_counter_;
public:
  Allocator(int size_of_memory) {
    chunks_list_.push_back(Chunk(1, size_of_memory , true, 0));
    memory_heap_.Insert(chunks_list_.begin());
    operations_counter_ = 0;
  }

  int allocateMemory(int size) {
    ++operations_counter_;
    allocated_chunks_.resize(operations_counter_, chunks_list_.end());

    if (memory_heap_.empty()) {
      return -1;
    }

    if (memory_heap_.GetMax()->length_ < size) {
      return -1;
    }

    list<Chunk>::iterator free_chunk = memory_heap_.ExtractMax();
    Chunk new_chunk(free_chunk->start_, size, false);
    allocated_chunks_[operations_counter_ - 1] =
        chunks_list_.insert(free_chunk, new_chunk);

    if (free_chunk->length_ == size) {
      chunks_list_.erase(free_chunk);
      return allocated_chunks_[operations_counter_ - 1]->start_;
    }

    free_chunk->length_ -= size;
    free_chunk->start_ += size;
    memory_heap_.Insert(free_chunk);
    return allocated_chunks_[operations_counter_ - 1]->start_;
  }

  void deallocateMemory(int num) {
    ++operations_counter_;
    if (allocated_chunks_[num - 1] == chunks_list_.end()) {
      return;
    }

    allocated_chunks_[num - 1]->is_free_ = true;

    // Merge with prev
    if (allocated_chunks_[num - 1] != chunks_list_.begin()) {
      list<Chunk>::iterator prev_chunk = allocated_chunks_[num - 1];
      --prev_chunk;
      if (prev_chunk->is_free_) {
        allocated_chunks_[num - 1]->length_ += prev_chunk->length_;
        allocated_chunks_[num - 1]->start_ = prev_chunk->start_;
        memory_heap_.Remove(prev_chunk->index_);
        chunks_list_.erase(prev_chunk);
      }
    }
    // Merge with next
    if (allocated_chunks_[num - 1] != --(chunks_list_.end())) {
      list<Chunk>::iterator next_chunk = allocated_chunks_[num - 1];
      ++next_chunk;
      if (next_chunk->is_free_) {
        allocated_chunks_[num - 1]->length_ += next_chunk->length_;
        memory_heap_.Remove(next_chunk->index_);
        chunks_list_.erase(next_chunk);
      }
    }

    memory_heap_.Insert(allocated_chunks_[num - 1]);
  }
};


void readInputToVector(vector<int> *vec) {
  int number_of_numbers, cur_number;
  scanf("%d", &number_of_numbers);
  for (int i = 0; i < number_of_numbers; ++i) {
    scanf("%d", &cur_number);
    vec->push_back(cur_number);
  }
}

void performRequests(const vector<int> &requests, vector<int> *output_vec,
                     Allocator *allocator) {
  for (vector<int>::const_iterator it = requests.begin(); it != requests.end();
  ++it) {
    if (*it > 0) {
      output_vec->push_back(allocator->allocateMemory(*it));
    }
    if (*it < 0) {
      allocator->deallocateMemory(-(*it));
    }
  }
}

void writeOutput(const vector<int> &vec) {
  for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    printf("%d\n", *it);
  }
}

int main() {
  int size_of_memory;
  scanf("%d", &size_of_memory);
  Allocator allocator(size_of_memory);
  vector<int> requests;
  readInputToVector(&requests);
  vector<int> output_vec;
  performRequests(requests, &output_vec, &allocator);
  writeOutput(output_vec);
  return 0;
}