結果
問題 | No.1711 Divide LCM |
ユーザー |
![]() |
提出日時 | 2021-10-15 23:12:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,338 ms / 4,000 ms |
コード長 | 3,664 bytes |
コンパイル時間 | 2,958 ms |
コンパイル使用メモリ | 207,144 KB |
実行使用メモリ | 75,308 KB |
最終ジャッジ日時 | 2024-09-17 18:11:54 |
合計ジャッジ時間 | 13,679 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; void dfs(vector<int> &ans, bool &ok, int &cnt, vector<unsigned long long> &hash, vector<unsigned long long> &ng, unsigned long long ch, int csz, int sz, int p){ if (p == cnt){ if (csz == sz){ auto itr = lower_bound(ng.begin(), ng.end(), ch); if (itr == ng.end()){ ok = true; } else if (*itr != ch){ ok = true; } } } else { if (csz < sz){ dfs(ans, ok, cnt, hash, ng, ch ^ hash[p], csz + 1, sz, p + 1); if (ok){ ans.push_back(p); return; } } dfs(ans, ok, cnt, hash, ng, ch, csz, sz, p + 1); } } int main(){ mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); int N; cin >> N; vector<int> m(N); vector<vector<int>> p(N), e(N); for (int i = 0; i < N; i++){ cin >> m[i]; p[i] = vector<int>(m[i]); e[i] = vector<int>(m[i]); for (int j = 0; j < m[i]; j++){ cin >> p[i][j] >> e[i][j]; } } vector<int> P; for (int i = 0; i < N; i++){ for (int j = 0; j < m[i]; j++){ P.push_back(p[i][j]); } } sort(P.begin(), P.end()); P.erase(unique(P.begin(), P.end()), P.end()); int cnt = P.size(); for (int i = 0; i < N; i++){ for (int j = 0; j < m[i]; j++){ p[i][j] = lower_bound(P.begin(), P.end(), p[i][j]) - P.begin(); } } vector<int> mx(cnt, -1); for (int i = 0; i < N; i++){ for (int j = 0; j < m[i]; j++){ mx[p[i][j]] = max(mx[p[i][j]], e[i][j]); } } vector<vector<int>> s(N); for (int i = 0; i < N; i++){ for (int j = 0; j < m[i]; j++){ if (mx[p[i][j]] == e[i][j]){ s[i].push_back(p[i][j]); } } } bool ok = true; for (int i = 0; i < N; i++){ if (s[i].size() == cnt){ ok = false; } } if (!ok){ cout << -1 << endl; } else { vector<unsigned long long> hash(cnt, 0); for (int i = 0; i < cnt; i++){ for (int j = 0; j < 64; j++){ hash[i] *= 2; hash[i] += mt() % 2; } } vector<unsigned long long> ng; for (int i = 0; i < N; i++){ int cnt2 = s[i].size(); for (int j = 0; j < (1 << cnt2); j++){ int sz = __builtin_popcount(j); unsigned long long S = 0; for (int k = 0; k < cnt2; k++){ if ((j >> k & 1) == 1){ S ^= hash[s[i][k]]; } } ng.push_back(S); } } sort(ng.begin(), ng.end()); ng.erase(unique(ng.begin(), ng.end()), ng.end()); vector<int> ans; for (int i = 2; i <= 9; i++){ unsigned long long chh = 0; bool ok2 = false; dfs(ans, ok2, cnt, hash, ng, chh, 0, i, 0); if (ok2){ break; } if (i == 2 && cnt >= 10000){ cout << -1 << endl; return 0; } } vector<int> A(N, 1); for (int i = 0; i < N; i++){ for (int j = 0; j < m[i]; j++){ for (int k = 0; k < e[i][j]; k++){ A[i] *= P[p[i][j]]; } } } int k = ans.size(); vector<vector<int>> S(k); for (int i = 0; i < N; i++){ for (int j = 0; j < k; j++){ bool ok2 = true; int cnt2 = s[i].size(); for (int l = 0; l < cnt2; l++){ if (s[i][l] == ans[j]){ ok2 = false; } } if (ok2){ S[j].push_back(A[i]); break; } } } cout << k << endl; for (int i = 0; i < k; i++){ int n = S[i].size(); cout << n; for (int j = 0; j < n; j++){ cout << ' ' << S[i][j]; } cout << endl; } } }