結果
問題 | No.1711 Divide LCM |
ユーザー | pockyny |
提出日時 | 2023-01-31 03:53:25 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,799 ms / 4,000 ms |
コード長 | 3,208 bytes |
コンパイル時間 | 2,247 ms |
コンパイル使用メモリ | 149,180 KB |
実行使用メモリ | 54,816 KB |
最終ジャッジ日時 | 2024-06-30 10:26:40 |
合計ジャッジ時間 | 16,305 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <iostream> #include <unordered_map> #include <random> #include <algorithm> using namespace std; typedef long long ll; unordered_map<int,int> pri; int a[100010][10],b[100010][10],A[100010],sz[100010]; vector<int> c[100010],pp; unordered_map<int,ll> hs; unordered_map<ll,bool> se,zob; ll inf = 1000000000000000; bool ok = false; vector<int> ans; bool used[100010]; void solve(int pos,int target_num,vector<int> now,ll val){ if(ok) return; if(now.size()==target_num){ // cout << "result = :"; // for(int x:now) cout << x << " "; // cout << "\n"; // cout << "value = " << val << "\n"; if(zob.find(val)==zob.end()){ ok = true; ans = now; } return; } if(now.size() + pp.size() - pos==target_num){ val ^= hs[pp[pos]]; now.push_back(pp[pos]); solve(pos + 1,target_num,now,val); }else{ for(int i=pos;i<(int)pp.size() + (int)now.size() - target_num + 1;i++){ val ^= hs[pp[i]]; now.push_back(pp[i]); solve(i + 1,target_num,now,val); val ^= hs[pp[i]]; now.pop_back(); } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int i,j,n; cin >> n; for(i=0;i<n;i++){ cin >> sz[i]; A[i] = 1; for(j=0;j<sz[i];j++){ cin >> a[i][j] >> b[i][j]; pri[a[i][j]] = max(pri[a[i][j]],b[i][j]); for(int k=0;k<b[i][j];k++) A[i] *= a[i][j]; } } for(i=0;i<n;i++){ for(j=0;j<sz[i];j++){ if(pri[a[i][j]]==b[i][j]) c[i].push_back(a[i][j]); } } std::random_device seed_gen; std::default_random_engine engine(seed_gen()); // 0以上inf以下の値を等確率で発生させる std::uniform_int_distribution<ll> dist(0, inf); for(auto x:pri) hs[x.first] = dist(engine); int mx = -1; for(i=0;i<n;i++){ mx = max(mx,(int)c[i].size()); ll val = 0; for(int p:c[i]) val ^= hs[p]; if(se.find(val)!=se.end()) continue; se[val] = true; for(j=0;j<(1<<c[i].size());j++){ ll val2 = 0; for(int k=0;k<c[i].size();k++){ if(j>>k&1) val2 ^= hs[c[i][k]]; } zob[val2] = true; } } if(mx==pri.size()){ cout << -1 << "\n"; return 0; } for(auto x:pri) pp.push_back(x.first); std::random_device seed_gen2; std::default_random_engine engine2(seed_gen2()); shuffle(pp.begin(),pp.end(),engine2); for(i=1;i<=10;i++){ vector<int> now; if(!ok) solve(0,i,now,0); } cout << ans.size() << "\n"; for(i=0;i<n;i++) used[i] = false; for(int p:ans){ vector<int> vec; for(i=0;i<n;i++){ if(used[i]) continue; bool f = true; for(int q:c[i]){ if(p==q) f = false; } if(f){ vec.push_back(A[i]); used[i] = true; } } cout << vec.size() << " "; for(int X:vec) cout << X << " "; cout << "\n"; } }