SRM436 Div2 Hard

1000

x[i] != y[i] なインデックスを見つけて、それ以下を x[i], y[i] と逆の大小関係になるようにする。
自前のBigIntは略。

BigInt f(string a, string b, int idx, int S)
{
  const int N = a.size();

  if (a[idx] < b[idx]) ; else {
    swap(a[idx], b[idx]);
    --S;
  }
  for (int i = idx + 1; i < N && S; ++i) {
    if (a[i] < b[i]) {
      swap(a[i], b[i]);
      --S;
    }
  }

  for (int i = 0; i < N; ++i) {
    if (a[i] == b[i]) return BigInt(a) * BigInt(b);
  }
  if (S % 2) swap(a[N - 1], b[N - 1]);
  return BigInt(a) * BigInt(b);
}

class DigitsSwap {
public:
  string maximalProduct(string x, string y, int swaps)
  {
    if (swaps == 0) return (BigInt(x) * BigInt(y)).toString();

    const int N = x.size();
    int idx = -1;

    for (int i = 0; i < N; ++i) {
      if (x[i] != y[i]) {
        idx = i;
        break;
      }
    }
    if (idx == -1) return (BigInt(x) * BigInt(y)).toString();

    BigInt a = f(x, y, idx, swaps);
    BigInt b = f(y, x, idx, swaps);

    if (a < b) return b.toString();
    else return a.toString();
  }
};