結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
9,596 KB |
testcase_01 | AC | 4 ms
9,036 KB |
testcase_02 | AC | 4 ms
9,404 KB |
testcase_03 | AC | 5 ms
8,980 KB |
testcase_04 | AC | 13 ms
9,700 KB |
testcase_05 | AC | 51 ms
9,928 KB |
testcase_06 | AC | 17 ms
9,024 KB |
testcase_07 | AC | 39 ms
9,500 KB |
testcase_08 | AC | 14 ms
9,492 KB |
testcase_09 | AC | 82 ms
11,288 KB |
testcase_10 | AC | 21 ms
9,700 KB |
testcase_11 | AC | 121 ms
11,876 KB |
testcase_12 | AC | 24 ms
10,564 KB |
testcase_13 | AC | 5 ms
9,332 KB |
testcase_14 | AC | 8 ms
9,780 KB |
testcase_15 | AC | 12 ms
9,144 KB |
testcase_16 | AC | 5 ms
8,640 KB |
testcase_17 | AC | 8 ms
9,356 KB |
testcase_18 | AC | 117 ms
20,700 KB |
testcase_19 | AC | 113 ms
20,300 KB |
testcase_20 | AC | 111 ms
20,228 KB |
testcase_21 | AC | 175 ms
27,416 KB |
testcase_22 | AC | 1,799 ms
34,944 KB |
testcase_23 | AC | 1,492 ms
54,816 KB |
testcase_24 | AC | 170 ms
20,136 KB |
testcase_25 | AC | 159 ms
18,964 KB |
testcase_26 | AC | 157 ms
19,072 KB |
testcase_27 | AC | 169 ms
20,848 KB |
testcase_28 | AC | 158 ms
20,008 KB |
testcase_29 | AC | 7 ms
9,468 KB |
testcase_30 | AC | 185 ms
22,160 KB |
testcase_31 | AC | 7 ms
10,276 KB |
testcase_32 | AC | 163 ms
24,640 KB |
testcase_33 | AC | 153 ms
24,520 KB |
testcase_34 | AC | 13 ms
9,076 KB |
testcase_35 | AC | 233 ms
16,556 KB |
testcase_36 | AC | 273 ms
18,572 KB |
testcase_37 | AC | 261 ms
18,888 KB |
testcase_38 | AC | 297 ms
34,036 KB |
testcase_39 | AC | 190 ms
27,636 KB |
testcase_40 | AC | 5 ms
9,012 KB |
testcase_41 | AC | 5 ms
9,212 KB |
testcase_42 | AC | 6 ms
8,944 KB |
testcase_43 | AC | 5 ms
9,444 KB |
testcase_44 | AC | 5 ms
9,600 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"; } }