順列都市。 - blanket log

順列を列挙するだけの問題ですが、
英文解釈を激しく間違ってWAを連発orz

... should be output in alphabetically ascending order.
An upper case letter goes before the corresponding lower case letter.

これ読んで即座に文字コード順 ( A < ... < Z < a < ... < z ) だと思ってしまった。
違うよー。 A < a < B < b < C < ... だよぅ。親切に the corresponding って言ってるじゃん。

std::lexicographical_compareって、大文字小文字についてはどうなるんだっけ？

よく分からないので自分で関数オブジェクトを定義。

class lexless {
public:
  inline bool operator()(const char a, const char b) {
    char la,lb;
    la = tolower(a);
    lb = tolower(b);
    if (la != lb) return la < lb;
    else if (isupper(a) && islower(b)) return true;
    return false;
  }
};

STL の algorithm に、next_permutation / prev_permutation なんてものがあるんですね。これを使うと一発で終了。強すぎ。
関数オブジェクト使わず、単に比較関数を定義して関数ポインタを渡しても良いんだけど、一般的に関数ポインタを介しての呼び出しはインライン化されないことが多く効率が落ちるらしい。

  cin >> str;
  sort(str.begin(), str.end(), lexless());
  do {
    cout << str << endl;
  } while (next_permutation(str.begin(), str.end(), lexless()));

こういう、あまり使いどころなさそうなものをピンポイントで使えると爽快です。
10098 も同じような問題で、next_permutation 使うと3分で書けるｗ