結果

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

ソースコード

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;
    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;
        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(t < 0) break;
            if(n == 0 && t == 0){
                output(i,k,0,0); return 0;
            }
            if(n == 0) break;
            if(t%G || t > maxt) continue;
            if(b3 == b4){
                long long three = min(t/G,0LL+b3),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