結果

問題 No.3680 セグメント釣り
コンテスト
ユーザー Rapca1256
提出日時 2026-09-05 16:14:58
言語 C++17
(gcc 15.3.0 + boost 1.92.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 265 ms / 2,000 ms
+ 146µs
コード長 1,326 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,156 ms
コンパイル使用メモリ 209,788 KB
実行使用メモリ 9,780 KB
最終ジャッジ日時 2026-09-05 16:15:07
合計ジャッジ時間 7,116 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i<(int) (n);i++)
using namespace std;
using ll = long long;
#define lrep(i, n) for(ll i = 0; i<(ll) (n);i++)
ll INF = LLONG_MAX;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;



int main(){
    ll t;
    cin >> t;
    lrep(_, t){
      ll sx, sy, tx, ty, nsx, ntx;
      
      cin >> sx >> sy >> tx >> ty;
      if(sx > tx){
        swap(sx, tx);
        swap(sy, ty);
      }
      nsx = sx; ntx = tx;
      ll k = sy, cost = INF;
      lrep(i, k){
        if(nsx == 0LL && ntx == 0LL) break;
        nsx /= 2LL;
        ntx /= 2LL;
      }
      if(sy <= ty){
        while(ntx - nsx > 0LL){
          if(cost >= (k - sy) + abs(k - ty) + ntx - nsx){
            cost = (k - sy) + abs(k - ty) + ntx - nsx;
          
          }
          k++;
          nsx /= 2LL;
          ntx /= 2LL;
        }
        cost = min(cost, (k - sy) + abs(k - ty) + ntx - nsx);
      }else{
        while(ntx - nsx > 0LL){
          if(cost >= 2LL*(k - sy) + ntx - nsx){
            cost = 2LL*(k - sy) + ntx - nsx;
          
          }
          k++;
          nsx /= 2LL;
          ntx /= 2LL;
        }
        cost = min(cost, 2LL*(k - sy) + ntx - nsx);
        cost += abs(sy - ty);
      }
    
      cout << cost << endl;
    }
    
    return 0;
}
0