IOI2008 1問目 (TYPE PRINTER) [C++]

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

namespace {
std::vector<char> operation;
std::string lastword;

void type(const std::string& s)
{
  std::string::const_iterator it,b1,b2,e1;
  if ( lastword.size() > s.size() ) {
    b1 = lastword.begin();
    e1 = lastword.end();
    b2 = s.begin();
  }
  else {
    b1 = s.begin();
    e1 = s.end();
    b2 = lastword.begin();
  }
  it = std::mismatch(b1,e1,b2).first;
  std::size_t matchlen = std::distance(b1,it);
  if ( matchlen < lastword.size() ) {
    for ( int i = 0; i < lastword.size()-matchlen; ++i ) {
      operation.push_back('-');
    }
  }
  it = s.begin();
  std::advance(it,matchlen);
  std::copy(it,s.end(), std::back_inserter(operation));
  operation.push_back('P');
  lastword = s;
}
}
int main()
{
  int n;
  std::cin >> n;
  std::vector<std::string> v;
  std::copy(std::istream_iterator<std::string>(std::cin),
      std::istream_iterator<std::string>(),
      std::back_inserter(v));
  std::sort(v.begin(),v.end());
  std::for_each(v.begin(),v.end(),type);
  std::vector<char> shortest_operation;
  shortest_operation.swap(operation);
  while ( std::next_permutation(v.begin(), v.end()) ) {
    operation.clear();
    lastword="";
    std::for_each(v.begin(),v.end(),type);
    if ( operation.size() < shortest_operation.size() )
      shortest_operation.swap(operation);
  }

  operation.swap(shortest_operation);
  std::cout << operation.size() << "\n";
  std::copy(operation.begin(), operation.end(), std::ostream_iterator<char>(std::cout, "\n"));
  return 0;
}

一応答えは正しく出るっぽいけど、 std::next_permutation とか使ってるからきっと単語数増えたらめちゃくちゃ遅い。

ちなみに制限は 単語数 1 <= N <= 25000 (但し、採点時にはNは18を超えない?)、実行時間1秒以内、使用メモリ64KiB以内 だそうです。

公式資料にはご丁寧にC++のI/O streamはボトルネックになるからprintf/scanfの使用を強く推奨します(意訳)って書いてある。うーむ