結果

問題 No.1286 Stone Skipping
コンテスト
ユーザー vineet jain
提出日時 2020-11-13 23:24:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,214 bytes
コンパイル時間 1,781 ms
コンパイル使用メモリ 168,080 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-22 22:16:51
合計ジャッジ時間 2,549 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 20 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
// #define ll int128_t
// #define rep(i,x,n) for(ll i=x;i<n;i++)
// #define rrep(i,x,n) for(ll i=x;i>=n;i--)
// using namespace std;
// ll calc(ll n){
//   ll c=0;
//   while(n>1) n/=2,c++;
//   return c;
// }
// ll cal2(ll idx){
//   ll ans=1;
//   while(idx--)ans*=2;
//   return ans;
// }
// void solve(){
//   ll d;
//   cin>>d;
//   ll init=d,mx=calc(d),ans=0;
//   ll res=cal2(80);
//   rrep(i,mx-1,0){
//     if((d-cal2(i+1)+1) >0) {d-= (cal2(i+1)-1); ans+= cal2(i);}
//     else if((d-cal2(i+1)+1) == 0) {d-= (cal2(i+1)-1); ans+=cal2(i); break;}
//     else res=min(res,ans+cal2(i));
//   }
//   res=min(res,init);
//   if(d<=0) res=min(res,ans);
//   if(d>0){
//     ans=0;
//     d=init;
//     rrep(i,mx,0){
//       if((d-cal2(i+1)+1) >0) {d-= (cal2(i+1)-1); ans+= cal2(i);}
//       else if((d-cal2(i+1)+1) == 0) {d-= (cal2(i+1)-1); ans+=cal2(i); break;}
//       else res=min(res,ans+cal2(i));
//     }
//     if(d<0) res=min(res,ans);
//   }
//   cout<<res<<endl;
// }
// int32_t main(){
//   ios_base::sync_with_stdio(false);
//   cin.tie(NULL);
//   cout.tie(NULL);
//   solve();
// }


#include <bits/stdc++.h>
#define ll long long
#define rep(i,x,n) for(ll i=x;i<n;i++)
#define rrep(i,x,n) for(ll i=x;i>=n;i--)
using namespace std;
ll calc(ll n){
  ll c=0;
  while(n>1) n/=2,c++;
  return c;
}
void solve(){
  ll d;
  cin>>d;
  ll init=d,mx=calc(d),ans=0;
  ll res=1LL<<62;
  rrep(i,mx-1,0){
    if(d-(1LL<<(i+1LL))+1LL >0) {d-= ((1LL<<(i+1LL))-1LL); ans+= (1LL<<i);}
    else if(d-(1LL<<(i+1LL))+1LL == 0) {d-= ((1LL<<(i+1LL))-1LL); ans+=( 1LL<<i); break;}
    else res=min(res,ans+(1LL<<i));
  }
  if(d>0){
    res=min(res,init);
    ll mx=ceil(log2(init));
    d=init;
    ans=0;
    // cout<<mx<<endl;
    while(d>0 && mx>0){
      if(d>=((1LL<<mx)-1)) d-=((1LL<<(mx))-1),ans+= (1LL<<(mx-1));
      else res=min(res,ans+(1LL<<(mx-1)));
      mx--;
    }
    // cout<<d<<" "<<ans<<endl;
    if(d<=0) res=min(res,ans);
  }
  else res=min({res,init,ans});
  cout<<res<<endl;
}
int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
}
0