結果

問題 No.2844 Birthday Party Decoration
コンテスト
ユーザー テナガザル
提出日時 2024-08-23 21:45:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 1,427 bytes
コンパイル時間 1,181 ms
コンパイル使用メモリ 115,192 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-23 21:45:33
合計ジャッジ時間 1,604 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

void solve()
{
  int n;
  long long x;
  cin >> n >> x;
  vector<int> flag(60);
  for (int i = 0; i < n; ++i)
  {
    int c;
    cin >> c;
    flag[c] = 1;
  }
  for (int i = 0; i < 60; ++i) if ((x >> i) & 1) flag[i] = 0;
  vector<long long> ls, rs;
  for (int i = 0; i < 60; ++i)
  {
    if (flag[i] == 0) continue;
    long long tmp = 1LL << i;
    long long l = 0, r = (1LL << 60);
    while (r - l > 1)
    {
      long long mid = (l + r) / 2;
      ((mid | tmp) <= x ? l : r) = mid;
    }
    if ((l | tmp) >= x) ls.push_back(-(1LL << 60));
    else ls.push_back((l | tmp));
    l = -1, r = ((1LL << 60) | (1LL << 59));
    while (r - l > 1)
    {
      long long mid = (l + r) / 2;
      ((mid | tmp) >= x ? r : l) = mid;
    }
    rs.push_back(r | tmp);
  }
  if (ls.empty())
  {
    cout << 0 << endl;
    return;
  }
  set<pair<long long, int>> l, r;
  for (int i = 0; i < ls.size(); ++i) l.insert({ls[i], i});
  long long mi = l.begin()->first;
  long long ans = 2LL * (x - mi);
  while (!l.empty())
  {
    auto [_, id] = *l.begin();
    l.erase(l.begin());
    r.insert({rs[id], id});
    long long mil = x;
    if (!l.empty()) mil = l.begin()->first;
    long long mar = r.rbegin()->first;
    ans = min(ans, (mar - mil) * 2LL);
  }
  cout << ans << endl;
}

int main()
{
  int t;
  cin >> t;
  while (t--) solve();
}
0