10901 - Ferry Loading III - UVA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define db(a) cout << #a << " = " << a << endl;
#define foreach(it,l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int main() {
 int c, n, t, m, val, kr = 0, kl = 0, cap = 0, time = 0, cont = 0;
 char direccion[20];
 scanf("%d", &c);
 for (int k = 0; k < c; k++) {
  queue<int> left, right;
  scanf("%d %d %d", &n, &t, &m);
  kr = kl = 0;
  vector<int> posiciones(m);
  cont = 0;
  for (int i = 0; i < m; i++) {
   scanf("%d %s", &val, direccion);
   if(strcmp(direccion,"left") == 0) 
    left.push(val), kl++,posiciones[cont++] = 0;
   else 
    right.push(val), kr++,posiciones[cont++] = 1;
  }
  vector<int> listaL(kl), listaR(kr);
  kl = kr = cap = time = 0;
  string ini = "left";
  while (!left.empty() || !right.empty()) {
   if (!left.empty() && !right.empty()) {
    if(left.front() > time && right.front() > time) {
     if(left.front() > right.front()) {
      time += right.front() - time;
      if(ini == "left") time += t;
      ini = "right";
     }
     else {
      time += left.front() - time;
      if(ini == "right") time += t;
      ini = "left";
     }
    }
   }
   else {
    if (left.empty()) {
     if (right.front() > time) {
      time += right.front() - time;
      if(ini == "left") time += t;
      ini = "right";
     }
    }
    else {
     if (left.front() > time) {
      time += left.front() - time;
      if(ini == "right") time += t;
      ini = "left";
     }
    }
   }
   if (ini == "left") {
    cap = 0;
    while (cap < n && !left.empty() && left.front() <= time) {
     //printf("left %d\n", time + t);
     listaL[kl++] = time + t;
     left.pop();
     cap++;
    }
    time += t;
    ini = "right";
   }
   else {
    cap = 0;
    while (cap < n && !right.empty() && right.front() <= time) {
     //printf("right %d\n", time + t);
     listaR[kr++] = time + t;
     right.pop();
     cap++;
    }
    time += t;
    ini = "left";
   }
  }
  kl = kr = 0;
  for (int i = 0; i < m; i++) {
   if (!posiciones[i])
    printf("%d\n", listaL[kl++]);
   else
    printf("%d\n", listaR[kr++]);
  }
  if(k + 1 != c) printf("\n");
 }
 return 0;
}