結果

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

ソースコード

diff # 

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

#pragma region Macros
using ll = long long;
#define int ll
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V<V<T>>;
#define IOS\
    ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);
#define FOR(i,l,r) for(int i=(l);i<int(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(int i=(l);i>=int(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define SORT(name) sort(name.begin(), name.end())
#define RSORT(name)\
    SORT(name);\
    reverse(all(name));
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
template <class T> inline void print(T x){ cout << x << '\n';}
template<typename T1,typename T2> inline void chmin(T1 &a, T2 b){ if(a > b) a = b; }
template<typename T1,typename T2> inline void chmax(T1 &a, T2 b){ if(a < b) a = b; }

const ll LLINF = (1LL<<62);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
#pragma endregion

const int MOD = 1000000007;

#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const int MAX_N = 100010;

int D;

bool Check(int x) {
    int cur = 0;
    while(x > 0) {
        cur += x;
        if(cur == D) { return true; }
        x /= 2;
    }
    return false;
}

signed main() {
    IOS;

    cin >> D;

    V<> j_min, j_max;

    j_min.pb(1);
    j_max.pb(1);
    while(j_max[j_max.size()-1] < LLINF) {
        j_min.pb(j_min[j_min.size()-1] * 2);
        j_max.pb(j_max[j_max.size()-1] * 2 + 1);
        if(j_max.size() > 1 && j_max[j_max.size()-1] <= j_max[j_max.size()-2]) {
            j_max.pop_back();
            j_min.pop_back();
            break;
        }
    }

    V<> sum_min(j_min.size()), sum_max(j_max.size());
    sum_min[0] = 1;
    sum_max[0] = 1;
    for(int i = 1; i < j_min.size(); ++i) {
        sum_min[i] = sum_min[i-1] + j_min[i];
        sum_max[i] = sum_max[i-1] + j_max[i];
    }

    // D が何回はねた時作れる可能性があるか
    int cnt = -1;
    REP(i, sum_min.size()) {
        if(sum_min[i] <= D && D <= sum_max[i]) {
            cnt = i;
            break;
        }
    }
    if(cnt == -1) {
        assert(false);
        print(D);
        return 0;
    }

    int lb = sum_min[cnt], ub = sum_max[cnt];
    if(ub - lb < 100000) {
        for(int cand = j_min[cnt]; cand <= j_max[cnt]; ++cand) {
            if(cand <= 0 || cand > D) { continue; }
            if(Check(cand)) {
                print(cand);
                return 0;
            }
        }
    }
    //DBG("lb: %lld ub: %lld\n", lb, ub);
    int cur = 1;
    REP(i, cnt) {
        int mid = (ub + lb) / 2;
        if(mid < D) {
            lb = mid;
            cur = cur * 2 + 1;
        }
        else {
            ub = mid;
            cur = cur * 2;
        }
    }
    //DBG("cur: %lld\n", cur);

    // 最終 lb +-100 あたりに答えありそう
    for(int cand = cur - 10000; cand <= cur + 10000; ++cand) {
        if(cand <= 0 || cand > D) { continue; }
        if(Check(cand)) {
            print(cand);
            return 0;
        }
    }

    print(D);

    return 0;
}
0