UVa 1203 - Argus C++ map and priority queue

Question

Solution to this UVa problem by using simple data structures like map and priority queue.

Solution

Since priority queue stores data in descending order but we needed ascending order, we simply stored negative instead of positive. Alternatively we might have to write our own comparing function.

Code

#include <iostream>
using namespace std;
#include <bits/stdc++.h>

priority_queue<pair<int, int> > pq;
map<int, int> m;

int main() {
  while (1) {
    string r;
    cin >> r;
    if (r == "#")
      break;
    int qno;
    cin >> qno;
    int p;
    cin >> p;
    m[qno] = p;
    pq.push(make_pair(-p, -qno));
  }
  int k;
  cin >> k;
  while (k--) {
    int q = pq.top().second;
    cout << -q << "\n";
    int val = pq.top().first;
    val -= m[-q];
    pq.pop();
    pq.push(make_pair(val, q));
  }
  return 0;
}