結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-08 22:32:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,271 bytes |
コンパイル時間 | 2,050 ms |
コンパイル使用メモリ | 186,716 KB |
実行使用メモリ | 5,684 KB |
最終ジャッジ日時 | 2024-11-16 19:23:41 |
合計ジャッジ時間 | 5,865 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 WA * 1 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:63:13: warning: 'ans' may be used uninitialized [-Wmaybe-uninitialized] 63 | cout << ans << endl; | ^~~ main.cpp:41:9: note: 'ans' was declared here 41 | int ans; | ^~~
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){int N, M, P;cin >> N >> M >> P;vector<int> A(N);for(int i = 0; i < N; i++){cin >> A[i];}vector<vector<int>> p(31);bool ok = false;for (int i = 0; i < N; i++){int t = 0;int tmp = A[i];while (tmp % P == 0){tmp /= P;t++;}if (tmp > 1){ok = true;}p[t].push_back(A[i]);}if (!ok){cout << -1 << endl;} else {for (int i = 0; i < 31; i++){sort(p[i].begin(), p[i].end(), greater<int>());}vector<int> B;for (int i = 0; i < 31; i++){if (!p[i].empty()){B.push_back(p[i][0]);}}int cnt = B.size();map<long long, int> mp;queue<long long> Q;Q.push(1);mp[1] = 0;int ans;while (!Q.empty()){long long v = Q.front();Q.pop();if (v > M){ans = mp[v];break;}if (v % P == 0){if (!mp.count(v / P)){mp[v / P] = mp[v] + 1;Q.push(v / P);}} else {for (int i = 0; i < cnt; i++){if (!mp.count(v * B[i])){mp[v * B[i]] = mp[v] + 1;Q.push(v * B[i]);}}}}cout << ans << endl;}}