結果

問題 No.3068 Speedrun (Hard)
ユーザー GOTKAKO
提出日時 2025-03-21 23:32:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,275 ms / 2,000 ms
コード長 2,476 bytes
コンパイル時間 2,721 ms
コンパイル使用メモリ 205,620 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-21 23:32:49
合計ジャッジ時間 13,937 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

long long extgcd(long long a, long long b, long long &x,long long &y){
    if(b == 0){x = 1,y = 0; return a;}
    long long g = extgcd(b,a%b,y,x);
    y -= a/b*x; return g;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N,T,idx = 0;
    vector<tuple<long long,long long,long long>> AB(4);
    for(auto &[a,b,p] : AB) cin >> a,p = idx++;
    cin >> N;
    for(auto &[a,b,p] : AB) cin >> b;
    auto memo = AB;
    sort(AB.begin(),AB.end(),[&](auto a,auto b){return get<0>(a) < get<0>(b);});
    cin >> T;

    auto [a1,b1,p1] = AB.at(0);
    auto [a2,b2,p2] = AB.at(1);
    auto [a3,b3,p3] = AB.at(2);
    auto [a4,b4,p4] = AB.at(3);
    long long count = 0;
    auto output = [&](long long i,long long k,long long l,long long m) -> void {
        //cout << count << endl;
        vector<long long> answer(4);
        answer.at(p1) = i;
        answer.at(p2) = k;
        answer.at(p3) = l;
        answer.at(p4) = m;
        assert(min({i,k,l,m}) >= 0);
        assert(i <= a1);
        assert(k <= a2);
        assert(l <= a3);
        assert(m <= a4);
        assert(i+k+l+m == N);
        assert(i*b1+k*b2+l*b3+m*b4 == T);
        //cout << i << " " << k << " " << l << " " << m << endl;
        for(long long i=0; i<4; i++) cout << answer.at(i) << (i==3?"\n":" ");
    };

    long long G = gcd(b3,b4),maxt = a3*b3+a4*b4;
    long long c3 = b4/G,c4 = b3/G;
    for(long long i=0; i<=a1; i++){
        for(long long k=0; k<=min(N-i,a2); k++){
            long long n = N-i-k,t = T-i*b1-k*b2;
            if(n == 0 && t == 0){
                output(i,k,0,0); return 0;
            }
            if(n <= 0 || t <= 0) break;
            if(t%G || t > maxt) continue;
            if(b3 == b4){
                if(t/G+i+k != N) continue;
                long long three = min(t/G,0LL+a3),four = t/G-three;
                output(i,k,three,four); return 0;
            }
            count++;
            long long l,m,g = extgcd(b3,b4,l,m);
            l *= t/G,m *= t/G;
            if((n-l-m)%(abs(c3-c4))) continue;
            long long change = (n-l-m)/(abs(c3-c4));
            if((change >= 0 && c3 > c4)||(change < 0 && c3 < c4)) l += c3*abs(change),m -= c4*abs(change); 
            else l -= c3*abs(change),m += c4*abs(change);

            if(0 <= l && l <= a3 && 0 <= m && m <= a4){
                output(i,k,l,m); return 0;
            }
        }
    }
    assert(false);
}
0