結果

問題 No.3375 Binary Grid
コンテスト
ユーザー areik
提出日時 2025-11-21 23:20:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 225 ms / 2,000 ms
コード長 2,014 bytes
コンパイル時間 3,844 ms
コンパイル使用メモリ 253,628 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-11-21 23:20:47
合計ジャッジ時間 5,814 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

using isize = size_t;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = long double;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(3);
  _main();
}

i32 pow(i32 x, i32 n) {
  i32 res = 1;
  i32 a = x;
  while (n > 0) {
    if (n & 1) res *= a;
    a *= a;
    n >>= 1;
  }
  return res;
}

void _main() {
  i64 t;
  cin >> t;
  for (;t--;) {
    i64 r, c;
    cin >> r >> c;
    c--;
    i64 ans = 0;
    i64 i = 1, j = 0;
    while (j < c) {
      ans += 1ll << j;
      i += 1ll << j;
      j++;
      assert(i / (1ll << j) % 2 == 1);
    }
    while ((i >> j) != (r >> j)) {
      assert((i >> j) < (r >> j));
      ans += 1ll << j;
      i += 1ll << j;
      j++;
      assert(i / (1ll << j) % 2 == 1);
    }
      // cout << i << " " << j << "  " << r << " " << c << " " << ans << "!\n";
    while (c < j) {
      bool ok = false;
      for (i64 k = c; k <= j; k++) {
        if (!(r >> k & 1)) {
          ok = true;
        }
      }
      if (ok) {
        if (r / (1ll << (c + 1)) % 2 == 0) {
          i64 x = r >> c << c;
          i64 nr = x + (1ll << c);
          c++;
          ans += nr - r;
          r = nr;
        } else {
          i64 nr = min(r + 1, (((r >> (c + 1)) + 1) << (c + 1)) - 1);
          c++;
          ans++;
          r = nr;
        }
      } else {
        if (i < r) {
          c++;
          ans++;
          r--;
        } else if (i > r) {
          c++;
          ans++;
          r++;
        } else {
          c++;
          ans++;
        }
      }
      // cout << i << " " << j << "  " << r << " " << c << " " << ans << "!\n";
    }
    // assert((i >> j) == (r >> j));
    ans += abs(i - r);
    cout << ans << "\n";
  }
}
0