結果

問題 No.2746 Bicolor Pyramid
コンテスト
ユーザー Naru820
提出日時 2025-02-11 18:14:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,566 bytes
コンパイル時間 834 ms
コンパイル使用メモリ 63,360 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-02-11 18:14:47
合計ジャッジ時間 2,132 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 赤と青のブロック数 (1 ≤ R,B ≤ 10^18)
    unsigned long long R, B;
    cin >> R >> B;
    
    // 総ブロック数と、どちらか多い方の数を求める
    unsigned long long total = R + B;
    unsigned long long M = max(R, B);
    
    // ピラミッドのレベル L に対して、
    // 必要ブロック数の合計 T(L) = L(L+1)(2L+1)/6  が total 以下であること
    // かつ、最大要求 L^2 が M 以下であることが必要条件（実は十分条件）です。
    //
    // 二分探索で、これらの条件を満たす最大の L を求めます。
    // (注: T(L) ≈ L^3/3 なので、L は O((R+B)^(1/3)) となり、
    //  R+B ≤ 2×10^18 なら L は数百万程度となります)
    
    unsigned long long low = 0, high = 2000000, ans = 0;
    while(low <= high){
        unsigned long long mid = (low + high) / 2;
        
        // T(mid) = 1^2 + 2^2 + ... + mid^2 = mid*(mid+1)*(2*mid+1)/6
        __int128 T = ( __int128) mid * (mid + 1) * (2*mid + 1);
        T /= 6;
        
        // 条件1: T(mid) <= total
        bool cond1 = (T <= total);
        // 条件2: mid^2 <= M
        __int128 sq = ( __int128) mid * mid;
        bool cond2 = (sq <= M);
        
        if(cond1 && cond2){
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    cout << ans << "\n";
    return 0;
}
0