BOJ 23042 - AND와 OR

BOJ 23042 - AND와 OR

연산이 무엇을 의미하는지를 잘 관찰해보자.

1011
1100

이 있을 때, 항상 다음과 같이 만들어주는게 이득이다.

1000
1111

$1$의 개수는 변하지 않고 더 작은 수에 있는 $1$이 더 큰수쪽으로 정확히 개수가 보존되며 이전된다고 생각할 수 있다.

곱에있어서 이것이 항상 더 최솟값을 내는 이유는 $a, b\ (a<b)$ 가 있을 때, $ab > (a-c)(b+c)$ 이기 때문이다.

$(a-c)(b+c)=ab-bc+ac-c^2$ 이기 때문이다. $c=2^k\ (0 \le k < 30)$

따라서 작은 수에 있는 비트들을 큰 수쪽으로 모두 움직여주는 문제인데,

각 비트에 대해서 투포인터로 구현하는 것이 단순하다.

난 솔직히 난이도 가리고풀어서 당연히 플레티넘인줄 알았는데 골드라 의외였다.

const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }
void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   sort(all(a));

   int ans = 1;

   for (int i = 0; i < 30; i++) {
      int l = 0, r = n - 1;
      int b = 1 << i;
      while (l < r) {
         while (r >= 0 && (a[r] & b))r--;
         while (l < n && !(a[l] & b))l++;
         if (l < r) a[r] ^= b, a[l] ^= b;
      }
   }
   for (int i = 0; i < n; i++) ans = md(ans * a[i]);

   cout << ans;
}