Fail Uva 10051

gistfile1.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

struct Pair {
  int idx;
  int face;
  Pair() : idx(-1), face(-1) {}
  Pair(int idx, int face) : idx(idx), face(face) {}
};

struct Cube {
  int colors[6];
  Pair preds[6];
};

struct Item {
  Pair p;
  int height;
  Item() : p(), height(-1) {}
  Item(int idx, int face, int height) : p(idx, face), height(height) {}
  bool operator<(const Item& other) const {
    return height < other.height;
  }
};

const char *names[] = {
  "front",
  "back",
  "left",
  "right",
  "top",
  "bottom"
};


int main() {
  setvbuf(stdin, NULL, _IOFBF, 10000);
  setvbuf(stdout, NULL, _IOFBF, 10000);
  Cube cubes[1024];
  Item tallest[1024][256];
  int n;
  int ctr = 0;
  while (scanf("%d", &n) == 1 && n) {
    if (ctr > 0) putchar('\n');
    for (int i = 0; i < 1024; ++i) fill(tallest[i], tallest[i]+256, Item());
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < 6; ++j) {
        scanf("%d", &cubes[i].colors[j]);
      }
      fill(cubes[i].preds, cubes[i].preds+6, Pair());
    }
    for (int i = n-1; i >= 0; --i) {
      Cube& cube = cubes[i];
      copy(tallest[i+1], tallest[i+1] + 256, tallest[i]);
      for (int j = 0; j < 6; ++j) {
        int top = cube.colors[j];
        int bot = cube.colors[j + ((j%2) ? -1 : 1)];
        if (tallest[i+1][bot].height != -1) {
          int new_height = tallest[i+1][bot].height + 1;
          if (new_height >= tallest[i][top].height) {
            tallest[i][top].p.idx = i;
            tallest[i][top].p.face = j;
            tallest[i][top].height = new_height;
            cube.preds[j].idx = tallest[i+1][bot].p.idx;
            cube.preds[j].face = tallest[i+1][bot].p.face;
          }
        } else if (tallest[i+1][top].height == -1) {
          tallest[i][top].height = 1;
          tallest[i][top].p.idx = i;
          tallest[i][top].p.face = j;
        }
      }
    }
    Item* max_el = max_element(tallest[0], tallest[0]+256);
    printf("Case #%d\n", ctr+1);
    printf("%d\n", max_el->height);
    for (Pair p = max_el->p; p.idx != -1; p = cubes[p.idx].preds[p.face]) {
      printf("%d %s\n", p.idx+1, names[p.face]);
    }
    ++ctr;
  }
  
  return 0;
}