結果
問題 | No.1711 Divide LCM |
ユーザー | pockyny |
提出日時 | 2023-01-31 03:53:25 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,611 ms / 4,000 ms |
コード長 | 3,208 bytes |
コンパイル時間 | 2,987 ms |
コンパイル使用メモリ | 146,324 KB |
実行使用メモリ | 54,996 KB |
最終ジャッジ日時 | 2023-09-12 22:58:52 |
合計ジャッジ時間 | 18,102 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
9,404 KB |
testcase_01 | AC | 4 ms
9,556 KB |
testcase_02 | AC | 5 ms
9,428 KB |
testcase_03 | AC | 5 ms
9,488 KB |
testcase_04 | AC | 12 ms
9,740 KB |
testcase_05 | AC | 52 ms
10,044 KB |
testcase_06 | AC | 17 ms
9,724 KB |
testcase_07 | AC | 39 ms
10,032 KB |
testcase_08 | AC | 13 ms
9,808 KB |
testcase_09 | AC | 78 ms
10,844 KB |
testcase_10 | AC | 22 ms
9,676 KB |
testcase_11 | AC | 118 ms
10,916 KB |
testcase_12 | AC | 23 ms
9,664 KB |
testcase_13 | AC | 5 ms
9,456 KB |
testcase_14 | AC | 8 ms
9,616 KB |
testcase_15 | AC | 12 ms
9,688 KB |
testcase_16 | AC | 5 ms
9,588 KB |
testcase_17 | AC | 9 ms
9,612 KB |
testcase_18 | AC | 103 ms
21,028 KB |
testcase_19 | AC | 109 ms
20,888 KB |
testcase_20 | AC | 102 ms
20,932 KB |
testcase_21 | AC | 150 ms
27,380 KB |
testcase_22 | AC | 1,611 ms
36,480 KB |
testcase_23 | AC | 1,322 ms
54,996 KB |
testcase_24 | AC | 155 ms
20,032 KB |
testcase_25 | AC | 147 ms
20,040 KB |
testcase_26 | AC | 144 ms
19,956 KB |
testcase_27 | AC | 157 ms
20,356 KB |
testcase_28 | AC | 151 ms
20,200 KB |
testcase_29 | AC | 7 ms
9,500 KB |
testcase_30 | AC | 149 ms
22,472 KB |
testcase_31 | AC | 7 ms
9,540 KB |
testcase_32 | AC | 141 ms
24,376 KB |
testcase_33 | AC | 132 ms
24,380 KB |
testcase_34 | AC | 13 ms
9,704 KB |
testcase_35 | AC | 212 ms
19,540 KB |
testcase_36 | AC | 251 ms
19,740 KB |
testcase_37 | AC | 244 ms
19,668 KB |
testcase_38 | AC | 231 ms
34,008 KB |
testcase_39 | AC | 150 ms
27,728 KB |
testcase_40 | AC | 5 ms
9,464 KB |
testcase_41 | AC | 6 ms
9,584 KB |
testcase_42 | AC | 6 ms
9,484 KB |
testcase_43 | AC | 6 ms
9,476 KB |
testcase_44 | AC | 5 ms
9,476 KB |
ソースコード
#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"; } }