結果

問題 No.3375 Binary Grid
コンテスト
ユーザー The Forsaking
提出日時 2025-12-04 16:34:21
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 54 ms / 2,000 ms
コード長 1,752 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,526 ms
コンパイル使用メモリ 195,256 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-12-04 16:34:24
合計ジャッジ時間 3,051 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:60:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~
main.cpp:62:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |         scanf("%lld%lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];

ll x, y;
void solve() {
    int p = (int)log2(x) + 1;
    ll t = 1ll << p - 1, res = t - 1;
    const ll cp = p, cx = x;
    if (y == cp) res += x - t;
    else {
        ll l = t, r = t + (1ll << cp - 1) - 1, f = 0;
        for (int i = cp - 1; i >= y; i--) {
            f++, res++;
            if (i == y) {
                res += max(0ll, abs(t - x) - f);
            } else if ((x >> i - 1) & 1) {
                l += (1ll << (i - 1));
                if (t < l) {
                    ll c = min(abs(t - l), f);
                    f -= c;
                    res += abs(t - l) - c;
                    t = l;
                } else if (t > r) {
                    ll c = min(abs(t - r), f);
                    f -= c;
                    res += abs(t - r) - c;
                    t = r;
                }
            } else {
                r -= (1ll << (i - 1));
                if (t != r + 1) {
                    ll c = min(abs(t - r - 1), f);
                    f -= c;
                    res += abs(t - r - 1) - c;
                    t = r + 1;
                }
                f = 0;
            }
            // printf("!! %lld %lld %lld %lld\n", l, r, t, res);
        }
    }
    printf("%lld\n", res);
}

int main() {
    // for (int i = 1; i <= 128; i++) {
    //     printf("%3d ", i);
    //     for (int j = 1; j < 9; j++) 
    //         putchar(i >> (j - 1) & 1 ? 'X' : ' ');
    //     puts("");
    // }
    // return 0;
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &x, &y);
        solve();
    }
    return 0;
}
0