結果

問題 No.1711 Divide LCM
ユーザー TKTYI
提出日時 2021-10-15 23:10:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,857 bytes
コンパイル時間 3,640 ms
コンパイル使用メモリ 246,780 KB
実行使用メモリ 10,528 KB
最終ジャッジ日時 2024-09-17 18:11:03
合計ジャッジ時間 9,588 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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[K-1-i]=1;
    do{
      vector<bool>T(N);
      REP(i,K)if(XX[i]){
        REP(j,N)if(!binary_search(ALL(R[i]),j))T[j]=1;
      }
      if(count(ALL(T),1)==N){
        cout<<k<<endl;
        REP(i,K)if(XX[i]){
          vector<ll>ans;
          REP(j,N)if(!binary_search(ALL(R[i]),j)&&T[j]){T[j]=0;ans.push_back(j);}
          cout<<ans.size();for(ll i:ans)cout<<" "<<A[i];cout<<endl;
        }
        return 0;
      }
    }while(next_permutation(ALL(X)));
    k++;
  }
  return 0;
}
0