結果
問題 | No.1711 Divide LCM |
ユーザー | LayCurse |
提出日時 | 2021-10-15 22:29:14 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 8,458 bytes |
コンパイル時間 | 3,203 ms |
コンパイル使用メモリ | 241,196 KB |
実行使用メモリ | 45,392 KB |
最終ジャッジ日時 | 2024-09-17 17:42:03 |
合計ジャッジ時間 | 11,784 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
22,884 KB |
testcase_01 | AC | 5 ms
15,944 KB |
testcase_02 | AC | 5 ms
15,952 KB |
testcase_03 | AC | 5 ms
15,816 KB |
testcase_04 | AC | 15 ms
16,200 KB |
testcase_05 | AC | 100 ms
17,368 KB |
testcase_06 | AC | 25 ms
16,244 KB |
testcase_07 | AC | 87 ms
17,096 KB |
testcase_08 | AC | 12 ms
16,392 KB |
testcase_09 | AC | 34 ms
20,836 KB |
testcase_10 | AC | 8 ms
18,376 KB |
testcase_11 | AC | 41 ms
21,596 KB |
testcase_12 | AC | 9 ms
14,340 KB |
testcase_13 | AC | 6 ms
15,816 KB |
testcase_14 | AC | 7 ms
15,972 KB |
testcase_15 | AC | 8 ms
17,992 KB |
testcase_16 | AC | 5 ms
13,776 KB |
testcase_17 | AC | 6 ms
14,048 KB |
testcase_18 | AC | 89 ms
34,600 KB |
testcase_19 | AC | 91 ms
32,640 KB |
testcase_20 | AC | 87 ms
34,764 KB |
testcase_21 | AC | 101 ms
45,392 KB |
testcase_22 | AC | 163 ms
30,100 KB |
testcase_23 | AC | 259 ms
32,428 KB |
testcase_24 | TLE | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
ソースコード
#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; int next_scomb(int len, int arr[], int lim){ int i; for(i=(len)-1;i>=(0);i--){ if(arr[i] < lim+i-len){ arr[i]++; i++; while(i < len){ arr[i] = arr[i-1] + 1; i++; } return 1; } arr[i] = 0; } for(i=(0);i<(len);i++){ arr[i] = i; } return 0; } 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'); } } inline void wt_L(unsigned x){ int s=0; char f[10]; while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(long long x){ int s=0; int m=0; char f[20]; 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'); } } inline void wt_L(unsigned long long x){ int s=0; char f[21]; while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } while(s--){ my_putchar_unlocked(f[s]+'0'); } } int WRITER_DOUBLE_DIGIT = 15; inline int writerDigit_double(){ return WRITER_DOUBLE_DIGIT; } inline void writerDigit_double(int d){ WRITER_DOUBLE_DIGIT = d; } inline void wt_L(double x){ const int d = WRITER_DOUBLE_DIGIT; int k; int r; double v; if(x!=x || (x==x+1 && x==2*x)){ my_putchar_unlocked('E'); my_putchar_unlocked('r'); my_putchar_unlocked('r'); return; } if(x < 0){ my_putchar_unlocked('-'); x = -x; } x += 0.5 * pow(0.1, d); r = 0; v = 1; while(x >= 10*v){ v *= 10; r++; } while(r >= 0){ r--; k = floor(x / v); if(k >= 10){ k = 9; } if(k <= -1){ k = 0; } x -= k * v; v *= 0.1; my_putchar_unlocked(k + '0'); } if(d > 0){ my_putchar_unlocked('.'); v = 1; for(r=(0);r<(d);r++){ v *= 0.1; k = floor(x / v); if(k >= 10){ k = 9; } if(k <= -1){ k = 0; } x -= k * v; my_putchar_unlocked(k + '0'); } } } inline void wt_L(const char c[]){ int i=0; for(i=0;c[i]!='\0';i++){ my_putchar_unlocked(c[i]); } } inline void wt_L(string &x){ int i=0; for(i=0;x[i]!='\0';i++){ my_putchar_unlocked(x[i]); } } 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 main(){ int i; rd(N); for(i=(0);i<(N);i++){ rd(m[i]); { int Q5VJL1cS; for(Q5VJL1cS=(0);Q5VJL1cS<(m[i]);Q5VJL1cS++){ rd(p[i][Q5VJL1cS]); rd(e[i][Q5VJL1cS]); } } } 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 t_ynMSdg; cLtraits_try_make_signed<remove_reference<decltype((*((int*)NULL)))>::type>::type KrdatlYV; if(N==0){ KrdatlYV = 0; } else{ KrdatlYV = A[0]; for(t_ynMSdg=(1);t_ynMSdg<(N);t_ynMSdg++){ KrdatlYV = GCD_L(KrdatlYV, A[t_ynMSdg]); } } g =KrdatlYV; 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(int s=2;;s++){ int d[s]; { if(k >= s){ int zT28qSmp; for(zT28qSmp=(0);zT28qSmp<(s);zT28qSmp++){ d[zT28qSmp] = zT28qSmp; } do{ { int j; for(i=(0);i<(N);i++){ int j; for(j=(0);j<(s);j++){ if(has[i].count(d[j]) == 0){ break; } } if(j == s){ goto szDqbNYU; } } wt_L(s); wt_L('\n'); for(j=(0);j<(s);j++){ 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 HOAyP4rA; if(ress==0){ wt_L('\n'); } else{ for(HOAyP4rA=(0);HOAyP4rA<(ress-1);HOAyP4rA++){ wt_L(res[HOAyP4rA]); wt_L(' '); } wt_L(res[HOAyP4rA]); wt_L('\n'); } } } return 0; } szDqbNYU:; } while(next_scomb(s,d,k)); } } } 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; // { // 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(int s=2;;s++){ // int d[s]; // rep_scomb(d,s,k){ // rep(i,N){ // rep(j,s) if(has[i].count(d[j]) == 0) break; // if(j == s) break_continue; // } // 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 0; // } // } // }