結果
問題 | 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, intsz, 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;}}}