SRM436 Div2 Hard

1000

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

view plainprint?

1. BigInt f(string a, string b, int idx, int S)  
2. {  
3.   const int N = a.size();  
4.   
5.   if (a[idx] < b[idx]) ; else {  
6.     swap(a[idx], b[idx]);  
7.     --S;  
8.   }  
9.   for (int i = idx + 1; i < N && S; ++i) {  
10.     if (a[i] < b[i]) {  
11.       swap(a[i], b[i]);  
12.       --S;  
13.     }  
14.   }  
15.   
16.   for (int i = 0; i < N; ++i) {  
17.     if (a[i] == b[i]) return BigInt(a) * BigInt(b);  
18.   }  
19.   if (S % 2) swap(a[N - 1], b[N - 1]);  
20.   return BigInt(a) * BigInt(b);  
21. }  
22.   
23. class DigitsSwap {  
24. public:  
25.   string maximalProduct(string x, string y, int swaps)  
26.   {  
27.     if (swaps == 0) return (BigInt(x) * BigInt(y)).toString();  
28.   
29.     const int N = x.size();  
30.     int idx = -1;  
31.   
32.     for (int i = 0; i < N; ++i) {  
33.       if (x[i] != y[i]) {  
34.         idx = i;  
35.         break;  
36.       }  
37.     }  
38.     if (idx == -1) return (BigInt(x) * BigInt(y)).toString();  
39.   
40.     BigInt a = f(x, y, idx, swaps);  
41.     BigInt b = f(y, x, idx, swaps);  
42.   
43.     if (a < b) return b.toString();  
44.     else return a.toString();  
45.   }  
46. };  

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();
  }
};