結果

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

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

ll msb(ll x){
  return (63-__builtin_clzll(x));
}

ll est(ll r,ll c){
  for(ll i=msb(r);i>=0;i--){
    if((r&(1ll<<i))==0){break;}
    if(i==c-1){return r-1;}
  }
  if((r+1)&(1ll<<c)){return est(r+1,c+1)+1;}
  if(r&(1ll<<c)){return est(r,c+1)+1;}
  ll md=(r%(1ll<<c));
  ll gap=(1ll<<c)-md;
  return est(r+gap,c+1)+gap;
}

using pi=pair<int,int>;

int dx8[8]={-1,-1,-1,0,0,1,1,1};
int dy8[8]={-1,0,1,-1,1,-1,0,1};

bool ok(int r,int c){
  if(r<1 || c<1){return false;}
  if(r&(1<<(c-1))){return true;}
  return false;
}

// int main(){
//   vector<vector<int>> dp(5000,vector<int>(100,1e9));
//   queue<pi> q;
//   q.push({1,1});
//   dp[1][1]=0;
//   while(!q.empty()){
//     auto od=q.front(); q.pop();
//     for(int k=0;k<8;k++){
//       int x=od.first+dx8[k];
//       int y=od.second+dy8[k];
//       if(!ok(x,y)){continue;}
//       if(x>=5000){continue;}
//       if(y>=100){continue;}
//       if(dp[x][y]>5e8){
//         dp[x][y]=dp[od.first][od.second]+1;
//         q.push({x,y});
//       }
//     }
//   }
//   for(int i=0;i<4096;i++){
//     for(int j=0;j<20;j++){
//       if(dp[i][j]>5e8){
//         continue;
//       }
//       else{
//         if(dp[i][j]!=est(i,j)){
//           cout << i << " " << j << " ";
//           cout << dp[i][j] << " " << est(i,j) << "\n";
//         }
//       }
//     }
//   }
//   // for(int i=0;i<60;i++){
//   //   for(int j=0;j<20;j++){
//   //     if(dp[i][j]>5e8){
//   //       printf("-- ");
//   //     }
//   //     else{
//   //       printf("%2d ",dp[i][j]);
//   //     }
//   //   }
//   //   printf("\n");
//   // }
//   return 0;
// }

int main(){
  int t;
  cin >> t;
  while(t--){
    ll r,c;
    cin >> r >> c;
    cout << est(r,c) << "\n";
  }
}
0