結果
問題 | No.1711 Divide LCM |
ユーザー | chineristAC |
提出日時 | 2021-08-14 13:41:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,683 bytes |
コンパイル時間 | 2,665 ms |
コンパイル使用メモリ | 169,944 KB |
実行使用メモリ | 814,144 KB |
最終ジャッジ日時 | 2023-10-17 19:52:42 |
合計ジャッジ時間 | 16,144 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 8 ms
4,348 KB |
testcase_09 | AC | 40 ms
4,348 KB |
testcase_10 | AC | 8 ms
4,348 KB |
testcase_11 | AC | 52 ms
4,348 KB |
testcase_12 | AC | 9 ms
4,348 KB |
testcase_13 | AC | 2 ms
4,348 KB |
testcase_14 | AC | 4 ms
4,348 KB |
testcase_15 | AC | 5 ms
4,348 KB |
testcase_16 | AC | 2 ms
4,348 KB |
testcase_17 | AC | 4 ms
4,348 KB |
testcase_18 | AC | 543 ms
232,920 KB |
testcase_19 | AC | 483 ms
150,820 KB |
testcase_20 | AC | 501 ms
164,540 KB |
testcase_21 | AC | 130 ms
10,960 KB |
testcase_22 | AC | 663 ms
31,676 KB |
testcase_23 | AC | 816 ms
99,408 KB |
testcase_24 | AC | 112 ms
9,812 KB |
testcase_25 | AC | 111 ms
9,224 KB |
testcase_26 | AC | 107 ms
7,112 KB |
testcase_27 | AC | 110 ms
8,252 KB |
testcase_28 | AC | 105 ms
7,124 KB |
testcase_29 | WA | - |
testcase_30 | AC | 144 ms
24,556 KB |
testcase_31 | AC | 3 ms
4,348 KB |
testcase_32 | AC | 131 ms
9,944 KB |
testcase_33 | AC | 130 ms
9,884 KB |
testcase_34 | AC | 9 ms
4,348 KB |
testcase_35 | AC | 130 ms
8,204 KB |
testcase_36 | AC | 138 ms
8,408 KB |
testcase_37 | AC | 138 ms
8,408 KB |
testcase_38 | MLE | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <iostream> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <algorithm> #include <cmath> #include <iomanip> #include <random> #include <stdio.h> #include <fstream> #include <functional> #include <cassert> #include <unordered_set> using namespace std; #define rep(i,n,c) for (int i=0;i<n;i+=c) #define append push_back #define all(x) (x).begin(), (x).end() template<class T> using vec = vector<T>; template<class T> using vvec = vec<vec<T>>; template<class T> using vvvec = vec<vvec<T>>; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<class T> bool chmin(T &a, T b){ if (a>b){ a = b; return true; } return false; } template<class T> bool chmax(T &a, T b){ if (a<b){ a = b; return true; } return false; } template<class T> T sum(vec<T> x){ T res=0; for (auto e:x){ res += e; } return res; } template<class T> void printv(vec<T> x){ for (auto e:x){ cout<<e<<" "; } cout<<"\n"; } int pow(int n,int k){ int res = 1; while (k){ if (k&1){ res *= n; } n *= n; k >>= 1; } return res; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int N; cin>>N; map<int,int> LCM; vec<int> A(N,1); unordered_set<ll> all_divisors; int m,p,e,t; for (int i=0;i<N;i++){ cin>>m; vec<int> D = {1}; for (int x=0;x<m;x++){ cin>>p>>e; t = pow(p,e); A[i] *= t; LCM[p]; chmax(LCM[p],t); vec<int> nD; for (auto d:D){ nD.append(d); nD.append(d*t); } D = nD; } for (auto d:D){ all_divisors.insert((ll)d); } } vec<int> P; for (auto [p,pe]:LCM){ P.append(pe); } int n = P.size(); deque<pair<ll,int>> deq = {{1,-1}}; ll prod = -1; while (!deq.empty()){ auto [v,k] = deq.front(); deq.pop_front(); if (!all_divisors.count(v)){ prod = v; break; } for (int i=k+1;i<n;i++){ if (v*P[i] <= 1000000000){ deq.append({v*P[i],i}); } else{ break; } } } if (prod==-1){ cout<<-1<<endl; return 0; } vec<int> selected_P; for (int i=0;i<n;i++){ if (prod%P[i]==0){ selected_P.append(P[i]); } } int k = selected_P.size(); vec<vec<int>> S(k,vec<int>(0)); for (int i=0;i<N;i++){ for (int j=0;j<k;j++){ if (A[i]%selected_P[j]){ S[j].append(A[i]); break; } } } cout<<k<<endl; for (int i=0;i<k;i++){ cout<<S[i].size()<<" "; printv(S[i]); } }