結果

問題 No.1330 Multiply or Divide
ユーザー hiro71687k
提出日時 2023-08-23 08:12:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,801 bytes
コンパイル時間 4,431 ms
コンパイル使用メモリ 264,116 KB
最終ジャッジ日時 2025-02-16 12:29:51
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll=long long;
using ld=long double;
ld pie=3.141592653589793;
ll mod=998244353;
ll inf=1009999999999999990;
int main(){
    ll n,m,p;
    cin >> n >> m >> p;
    vector<ll>a(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<ll>b;
    map<ll,ll>mmm;
    for (ll i = 0; i < n; i++)
    {
        if (a[i]!=1&&mmm[a[i]]==0)
        {
            b.push_back(a[i]);
            mmm[a[i]]=1;
        }
    }
    n=b.size();
    a=b;
    map<ll,ll>memo;
    memo[1]=1;
    priority_queue<ll>pq;
    map<ll,ll>mm;
    pq.push(1);
    ll ans=32;
    ll now=0;
    while (!pq.empty())
    {
        now++;
        if (now>n*20)
        {
            cout << -1 << endl;
            return 0;
        }
        
        ll v=pq.top();
        pq.pop();
        mm[v]=0;
        if (v>=m)
        {
            ans=min(ans,memo[v]);
        }
        if (ans<=memo[v])
        {
            continue;
        }
        if (v%p==0)
        {
            v/=p;
            ll x=memo[v];
            if (x==0||x>memo[v*p]+1)
            {
                memo[v]=memo[v*p]+1;
                if (mm[v]==0)
                {
                    pq.push(v);
                    mm[v]++;
                }
            }
            continue;
        }
        for (ll i = 0; i < n; i++)
        {
            ll x=memo[v*a[i]];
            if (x==0||x>memo[v]+1)
            {
                memo[v*a[i]]=memo[v]+1;
                if (mm[v*a[i]]==0)
                {
                    pq.push(v*a[i]);
                    mm[v*a[i]]++;
                }
            }
        }
    }
    if (ans==32)
    {
        cout << -1 << endl;
    }else{
        cout << ans-1 << endl;
    }
}
0