BOJ 11538 - Pyro Tubes

BOJ 11538 - Pyro Tubes

실버 5문제여서 그냥 $O(n^2)$ 구현했는데 그냥 TLE당했다.

$L$ 제한을 보니 25만이라 적절히 검사해 통과할 수 있었다.

int bcnt(ll x) { return __builtin_popcountll(x); }  
int rz(ll x) { return __builtin_ctzll(x); }  
int lz(ll x) { return __builtin_clzll(x); }  
int msb(ll x) { return 63 - lz(x); }  
void solve() {  
  
   vi a;  
   while (1) {  
      int L;  
      cin >> L;  
      if (L == -1) break;  
      a.pb(L);  
   }  
  
   bitset<555555> used;  
   for (int i: a) used[i] = 1;  
   int n = sz(a);  
   for (int i = 0; i < n; i++) {  
      int ans = 0;  
      for (int j = 0; j < 18; j++) {  
         int t = a[i] ^ (1 << j);  
         if (used[t] && t > a[i]) ans++;  
         for (int k = j + 1; k < 18; k++) {  
            t = a[i] ^ (1 << j) ^ (1 << k);  
            if (used[t] && t > a[i]) ans++;  
         }  
      }  
      cout << a[i] << ':' << ans << endl;  
   }  
}