結果
問題 | No.1711 Divide LCM |
ユーザー | LayCurse |
提出日時 | 2021-10-15 22:47:58 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,029 ms / 4,000 ms |
コード長 | 6,891 bytes |
コンパイル時間 | 5,280 ms |
コンパイル使用メモリ | 273,564 KB |
実行使用メモリ | 51,712 KB |
最終ジャッジ日時 | 2023-10-17 20:41:50 |
合計ジャッジ時間 | 20,817 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
15,948 KB |
testcase_01 | AC | 5 ms
15,948 KB |
testcase_02 | AC | 5 ms
15,944 KB |
testcase_03 | AC | 6 ms
16,068 KB |
testcase_04 | AC | 11 ms
16,428 KB |
testcase_05 | AC | 42 ms
19,596 KB |
testcase_06 | AC | 16 ms
16,480 KB |
testcase_07 | AC | 37 ms
19,352 KB |
testcase_08 | AC | 18 ms
16,640 KB |
testcase_09 | AC | 140 ms
23,068 KB |
testcase_10 | AC | 26 ms
16,528 KB |
testcase_11 | AC | 203 ms
24,008 KB |
testcase_12 | AC | 29 ms
16,536 KB |
testcase_13 | AC | 5 ms
16,036 KB |
testcase_14 | AC | 11 ms
16,196 KB |
testcase_15 | AC | 17 ms
16,304 KB |
testcase_16 | AC | 6 ms
16,040 KB |
testcase_17 | AC | 10 ms
16,200 KB |
testcase_18 | AC | 98 ms
35,284 KB |
testcase_19 | AC | 102 ms
35,284 KB |
testcase_20 | AC | 96 ms
35,248 KB |
testcase_21 | AC | 108 ms
48,108 KB |
testcase_22 | AC | 765 ms
32,744 KB |
testcase_23 | AC | 987 ms
34,980 KB |
testcase_24 | AC | 747 ms
39,236 KB |
testcase_25 | AC | 642 ms
39,224 KB |
testcase_26 | AC | 264 ms
39,232 KB |
testcase_27 | AC | 601 ms
39,316 KB |
testcase_28 | AC | 426 ms
38,984 KB |
testcase_29 | AC | 12 ms
16,120 KB |
testcase_30 | AC | 641 ms
41,008 KB |
testcase_31 | AC | 10 ms
16,108 KB |
testcase_32 | AC | 1,029 ms
47,040 KB |
testcase_33 | AC | 143 ms
47,044 KB |
testcase_34 | AC | 21 ms
16,476 KB |
testcase_35 | AC | 587 ms
36,920 KB |
testcase_36 | AC | 668 ms
36,916 KB |
testcase_37 | AC | 512 ms
36,904 KB |
testcase_38 | AC | 224 ms
51,712 KB |
testcase_39 | AC | 273 ms
48,192 KB |
testcase_40 | AC | 6 ms
16,076 KB |
testcase_41 | AC | 5 ms
16,080 KB |
testcase_42 | AC | 6 ms
16,092 KB |
testcase_43 | AC | 6 ms
16,096 KB |
testcase_44 | AC | 6 ms
16,120 KB |
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("inline") #include<bits/stdc++.h> using namespace std; template<class T> struct cLtraits_identity{ using type = T; } ; template<class T> using cLtraits_try_make_signed = typename conditional< is_integral<T>::value, make_signed<T>, cLtraits_identity<T> >::type; void*wmem; char memarr[96000000]; template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){ walloc1d(arr, x2-x1, mem); (*arr) -= x1; } inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } template<class T, class S> inline T pow_L(T a, S b){ T res = 1; res = 1; for(;;){ if(b&1){ res *= a; } b >>= 1; if(b==0){ break; } a *= a; } return res; } inline double pow_L(double a, double b){ return pow(a,b); } template<class T, class U> inline T GCD_L(T a, U b){ T r; while(b){ r=a; a=b; b=r%a; } return a; } template<class S, class T> inline S chmax(S &a, T b){ if(a<b){ a=b; } return a; } int N; int A[100000]; set<int> has[100000]; int m[100000]; int p[100000][30]; int e[100000][30]; int arr[100000][30]; int k; int g; int tmp; int ress; int res[100000]; int ok[100000]; map<int,int> ind; map<int,int> mx; int s; int d[100]; int solve(int dep, int rem, int lis[], int st = 0, void *mem = wmem){ int i; if(rem == 0){ int j; wt_L(s); wt_L('\n'); for(j=(0);j<(s);j++){ int i; ress = 0; for(i=(0);i<(N);i++){ if(!ok[i] && has[i].count(d[j])==0){ res[ress++] = A[i]; ok[i] = 1; } } wt_L(ress); wt_L(' '); { int cTE1_r3A; if(ress==0){ wt_L('\n'); } else{ for(cTE1_r3A=(0);cTE1_r3A<(ress-1);cTE1_r3A++){ wt_L(res[cTE1_r3A]); wt_L(' '); } wt_L(res[cTE1_r3A]); wt_L('\n'); } } } return 1; } if(dep == s){ return 0; } int*nx; int sz; walloc1d(&nx, rem, &mem); for(i=(st);i<(k);i++){ int j; sz = 0; for(j=(0);j<(rem);j++){ if(has[lis[j]].count(i)){ nx[sz++] = lis[j]; } } if(sz == rem){ continue; } d[dep] = i; if(solve(dep+1, sz, nx, i+1, mem)){ return 1; } } return 0; } int main(){ int i; wmem = memarr; rd(N); for(i=(0);i<(N);i++){ rd(m[i]); { int a2conNHc; for(a2conNHc=(0);a2conNHc<(m[i]);a2conNHc++){ rd(p[i][a2conNHc]); rd(e[i][a2conNHc]); } } } for(i=(0);i<(N);i++){ int j; A[i] = 1; for(j=(0);j<(m[i]);j++){ A[i] *=(pow_L(p[i][j],e[i][j])); } } int ZIeRIny5; cLtraits_try_make_signed<remove_reference<decltype((*((int*)NULL)))>::type>::type iMWUTgY_; if(N==0){ iMWUTgY_ = 0; } else{ iMWUTgY_ = A[0]; for(ZIeRIny5=(1);ZIeRIny5<(N);ZIeRIny5++){ iMWUTgY_ = GCD_L(iMWUTgY_, A[ZIeRIny5]); } } g =iMWUTgY_; for(i=(0);i<(N);i++){ int j; for(j=(0);j<(m[i]);j++){ tmp = g; while(tmp % p[i][j] == 0){ tmp /= p[i][j]; e[i][j]--; } } } for(i=(0);i<(N);i++){ int j; for(j=(0);j<(m[i]);j++){ if(e[i][j]){ if(ind.count(p[i][j]) == 0){ ind[p[i][j]] = k++; } chmax(mx[p[i][j]], e[i][j]); } } } for(i=(0);i<(N);i++){ int j; for(j=(0);j<(m[i]);j++){ if(e[i][j] && mx[p[i][j]] == e[i][j]){ has[i].insert(ind[p[i][j]]); } } } for(i=(0);i<(N);i++){ if(has[i].size() == k){ wt_L(-1); wt_L('\n'); return 0; } } for(s=2;;s++){ int lis[N]; for(i=(0);i<(N);i++){ lis[i] = i; } if(solve(0, N, lis)){ break; } } return 0; } // cLay version 20210926-1 // --- original code --- // int N, A[1d5]; set<int> has[]; // int m[1d5], p[1d5][30], e[1d5][30], arr[1d5][30], k, g, tmp; // int ress, res[1d5], ok[]; // map<int,int> ind, mx; // // int s, d[100]; // // int solve(int dep, int rem, int lis[], int st = 0, void *mem = wmem){ // if(rem == 0){ // wt(s); // rep(j,s){ // ress = 0; // rep(i,N) if(!ok[i] && has[i].count(d[j])==0) res[ress++] = A[i], ok[i] = 1; // wt(ress, res(ress)); // } // return 1; // } // if(dep == s) return 0; // // int *nx, sz; // walloc1d(&nx, rem, &mem); // rep(i,st,k){ // sz = 0; // rep(j,rem) if(has[lis[j]].count(i)) nx[sz++] = lis[j]; // if(sz == rem) continue; // d[dep] = i; // if(solve(dep+1, sz, nx, i+1, mem)) return 1; // } // return 0; // } // // { // rd(N); // rep(i,N) rd(m[i],(p[i],e[i])(m[i])); // rep(i,N){ // A[i] = 1; // rep(j,m[i]) A[i] *= p[i][j]**e[i][j]; // } // g = gcd(A(N)); // rep(i,N) rep(j,m[i]){ // tmp = g; // while(tmp % p[i][j] == 0) tmp /= p[i][j], e[i][j]--; // } // rep(i,N) rep(j,m[i]) if(e[i][j]){ // if(ind.count(p[i][j]) == 0) ind[p[i][j]] = k++; // mx[p[i][j]] >?= e[i][j]; // } // rep(i,N) rep(j,m[i]) if(e[i][j] && mx[p[i][j]] == e[i][j]) has[i].insert(ind[p[i][j]]); // rep(i,N) if(has[i].size() == k) wt(-1), return 0; // // for(s=2;;s++){ // int lis[N]; // rep(i,N) lis[i] = i; // if(solve(0, N, lis)) break; // } // }