結果
問題 | No.1711 Divide LCM |
ユーザー |
|
提出日時 | 2021-10-15 23:31:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 711 ms / 4,000 ms |
コード長 | 4,073 bytes |
コンパイル時間 | 2,785 ms |
コンパイル使用メモリ | 211,320 KB |
最終ジャッジ日時 | 2025-01-25 01:14:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < n; i++)#define rep2(i, x, n) for (int i = x; i <= n; i++)#define rep3(i, x, n) for (int i = x; i >= n; i--)#define each(e, v) for (auto &e : v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;template <typename T>bool chmax(T &x, const T &y) {return (x < y) ? (x = y, true) : false;}template <typename T>bool chmin(T &x, const T &y) {return (x > y) ? (x = y, true) : false;}template <typename T>int flg(T x, int i) {return (x >> i) & 1;}template <typename T>void print(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');}template <typename T>void printn(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << '\n';}template <typename T>int lb(const vector<T> &v, T x) {return lower_bound(begin(v), end(v), x) - begin(v);}template <typename T>int ub(const vector<T> &v, T x) {return upper_bound(begin(v), end(v), x) - begin(v);}template <typename T>void rearrange(vector<T> &v) {sort(begin(v), end(v));v.erase(unique(begin(v), end(v)), end(v));}template <typename T>vector<int> id_sort(const vector<T> &v, bool greater = false) {int n = v.size();vector<int> ret(n);iota(begin(ret), end(ret), 0);sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });return ret;}struct io_setup {io_setup() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;const int inf = (1 << 30) - 1;const ll INF = (1LL << 60) - 1;const int MOD = 1000000007;// const int MOD = 998244353;vector<int> used;vector<int> qs;ll ans = -1;void rec(int k, int i, ll x) {if (ans != -1) return;if (k == 0) {if (*lower_bound(all(used), x) != x) ans = x;return;}for (int j = i + 1; j < sz(qs); j++) {rec(k - 1, j, x * qs[j]);if (ans != -1) return;}}int main() {int N;cin >> N;int MAX = 1000000;vector<int> M(MAX + 1, 0);vector<vector<pii>> ps(N);vector<int> A(N, 1);rep(i, N) {int K;cin >> K;rep(j, K) {int p, e;cin >> p >> e;ps[i].eb(p, e);chmax(M[p], e);rep(k, e) A[i] *= p;}}// print(A);int K = 0;vector<int> id(MAX + 1, -1);rep(i, MAX + 1) {if (M[i] > 0) {id[i] = K++;int x = 1;rep(j, M[i]) x *= i;qs.eb(x);}}vector<vector<int>> ids(N);rep(i, N) {each(e, ps[i]) {if (M[e.first] == e.second) ids[i].eb(id[e.first]);}if (sz(ids[i]) == K) {cout << "-1\n";return 0;}}// rep(i, N) print(ids[i]);rep(i, N) {int T = sz(ids[i]);rep(j, 1 << T) {int x = 1;rep(k, T) {if (flg(j, k)) x *= qs[ids[i][k]];}used.eb(x);}}rearrange(used);// print(used);rep2(i, 2, 100) {rec(i, -1, 1);if (ans != -1) break;}vector<vector<int>> res;vector<bool> u(N, false);// cout << ans << '\n';int C = 0;rep(i, K) {if (ans % qs[i] == 0) {vector<int> tmp;rep(j, N) {if (u[j]) continue;if (A[j] % qs[i] != 0) tmp.eb(A[j]), u[j] = true;}C++, res.eb(tmp);ans /= qs[i];}}cout << C << '\n';rep(i, C) {cout << sz(res[i]) << ' ';print(res[i]);}}