結果
問題 | No.1711 Divide LCM |
ユーザー |
|
提出日時 | 2021-10-15 23:34:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,944 bytes |
コンパイル時間 | 3,759 ms |
コンパイル使用メモリ | 249,436 KB |
実行使用メモリ | 25,456 KB |
最終ジャッジ日時 | 2024-09-17 18:39:06 |
合計ジャッジ時間 | 20,490 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 RE * 2 |
other | AC * 5 RE * 37 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;typedef long long int ll;typedef long double ld;#define FOR(i,l,r) for(ll i=l;i<r;i++)#define REP(i,n) FOR(i,0,n)#define RFOR(i,l,r) for(ll i=r-1;i>=l;i--)#define RREP(i,n) RFOR(i,0,n)#define ALL(x) x.begin(),x.end()#define P pair<ll,ll>#define F first#define S second#define BS(A,x) binary_search(ALL(A),x)#define LB(A,x) (ll)(lower_bound(ALL(A),x)-A.begin())#define UB(A,x) (ll)(upper_bound(ALL(A),x)-A.begin())#define COU(A,x) UB(A,x)-LB(A,x)template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;//using mint=modint1000000007;using mint=modint998244353;signed main(){ll N;cin>>N;vector<ll>A(N,1);vector<vector<P>>X(N);set<ll>prime;REP(i,N){ll m;cin>>m;REP(j,m){ll p,e;cin>>p>>e;prime.insert(p);X[i].push_back(P(p,e));A[i]*=pow(p,e);}}ll K=prime.size();vector<ll>p;for(auto i:prime)p.push_back(i);vector<ll>MAX(K);REP(i,N)REP(j,X[i].size())MAX[LB(p,X[i][j].F)]=max(MAX[LB(p,X[i][j].F)],X[i][j].S);vector<vector<ll>>Q(N),R(K);REP(i,N)REP(j,X[i].size())if(MAX[LB(p,X[i][j].F)]==X[i][j].S)Q[i].push_back(LB(p,X[i][j].F));REP(i,N)if(Q[i].size()==K){cout<<-1<<endl;return 0;}REP(i,N)for(ll j:Q[i])R[j].push_back(i);ll k=2;while(1){vector<bool>XX(K);REP(i,k)XX[i]=1;sort(ALL(X));do{set<ll>T;REP(i,K)if(XX[i]){if(T.size()==0)for(ll j:R[i])T.insert(j);else for(ll j:T)if(!binary_search(ALL(R[i]),j))T.erase(T.find(j));}if(T.size()==0){cout<<k<<endl;vector<bool>TT(N,1);REP(i,K)if(XX[i]){vector<ll>ans;REP(j,N)if(!binary_search(ALL(R[i]),j)&&TT[j]){TT[j]=0;ans.push_back(j);}cout<<ans.size();for(ll i:ans)cout<<" "<<A[i];cout<<endl;}return 0;}}while(next_permutation(ALL(XX)));k++;}return 0;}