結果
問題 | No.1711 Divide LCM |
ユーザー | 沙耶花 |
提出日時 | 2021-10-15 22:46:19 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,816 bytes |
コンパイル時間 | 5,019 ms |
コンパイル使用メモリ | 282,556 KB |
実行使用メモリ | 94,184 KB |
最終ジャッジ日時 | 2023-10-17 20:39:50 |
合計ジャッジ時間 | 26,934 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 4 ms
4,348 KB |
testcase_04 | AC | 19 ms
4,548 KB |
testcase_05 | AC | 107 ms
6,112 KB |
testcase_06 | AC | 29 ms
4,576 KB |
testcase_07 | AC | 78 ms
5,816 KB |
testcase_08 | AC | 22 ms
4,800 KB |
testcase_09 | AC | 140 ms
8,492 KB |
testcase_10 | AC | 22 ms
4,640 KB |
testcase_11 | AC | 214 ms
9,968 KB |
testcase_12 | AC | 22 ms
4,644 KB |
testcase_13 | AC | 3 ms
4,348 KB |
testcase_14 | AC | 9 ms
4,348 KB |
testcase_15 | AC | 12 ms
4,348 KB |
testcase_16 | AC | 3 ms
4,348 KB |
testcase_17 | AC | 8 ms
4,348 KB |
testcase_18 | AC | 294 ms
26,076 KB |
testcase_19 | AC | 284 ms
26,076 KB |
testcase_20 | AC | 301 ms
26,072 KB |
testcase_21 | AC | 418 ms
33,920 KB |
testcase_22 | TLE | - |
testcase_23 | AC | 3,460 ms
94,184 KB |
testcase_24 | AC | 435 ms
26,504 KB |
testcase_25 | AC | 434 ms
25,536 KB |
testcase_26 | AC | 419 ms
24,140 KB |
testcase_27 | AC | 388 ms
25,672 KB |
testcase_28 | AC | 375 ms
24,040 KB |
testcase_29 | AC | 5 ms
4,348 KB |
testcase_30 | AC | 440 ms
34,692 KB |
testcase_31 | AC | 4 ms
4,348 KB |
testcase_32 | AC | 388 ms
37,032 KB |
testcase_33 | AC | 390 ms
37,036 KB |
testcase_34 | AC | 17 ms
4,612 KB |
testcase_35 | AC | 511 ms
24,944 KB |
testcase_36 | AC | 571 ms
25,888 KB |
testcase_37 | AC | 576 ms
25,920 KB |
testcase_38 | AC | 492 ms
42,272 KB |
testcase_39 | AC | 450 ms
39,344 KB |
testcase_40 | AC | 4 ms
4,348 KB |
testcase_41 | AC | 4 ms
4,348 KB |
testcase_42 | AC | 4 ms
4,348 KB |
testcase_43 | AC | 5 ms
4,348 KB |
testcase_44 | AC | 5 ms
4,348 KB |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 int main(){ int N; cin>>N; vector<map<int,int>> mp(N); map<int,int> LCA; vector<long long> v(N,1); rep(i,N){ int m; cin>>m; rep(j,m){ int p,e; cin>>p>>e; mp[i][p] = e; LCA[p] = max(LCA[p],e); rep(k,e)v[i] *= p; } } map<int,int> pos; int cur = 0; vector<int> ps(LCA.size()); for(auto a:LCA){ pos[a.first] = cur; ps[cur] = a.first; cur++; } set<vector<int>> S; vector<vector<int>> tt(N); rep(i,N){ vector<int> t; for(auto a:mp[i]){ if(a.second == LCA[a.first]){ t.push_back(pos[a.first]); } } sort(t.begin(),t.end()); tt[i] = t; if(S.count(t))continue; rep(j,1<<t.size()){ vector<int> nt; rep(k,t.size()){ if((j>>k)&1)nt.push_back(t[k]); } S.insert(nt); } } //cout<<'a'<<endl; vector<vector<int>> t(cur); rep(i,cur)t[i] = {i}; while(true){ if(t.size()==0){ cout<<-1<<endl; return 0; } vector<vector<int>> nt; rep(i,t.size()){ int last = t[i].back(); for(int j=last+1;j<cur;j++){ vector<int> temp = t[i]; temp.push_back(j); if(!S.count(temp)){ cout<<temp.size()<<endl; vector<vector<int>> ans(temp.size()); rep(i,N){ rep(j,temp.size()){ if(binary_search(tt[i].begin(),tt[i].end(),temp[j]))continue; ans[j].push_back(v[i]); break; } } rep(i,temp.size()){ cout<<ans[i].size(); rep(j,ans[i].size()){ cout<<' '; cout<<ans[i][j]; } cout<<endl; } return 0; } nt.push_back(temp); } } swap(t,nt); } return 0; }