結果

問題 No.1711 Divide LCM
ユーザー LayCurseLayCurse
提出日時 2021-10-15 22:47:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 883 ms / 4,000 ms
コード長 6,891 bytes
コンパイル時間 4,563 ms
コンパイル使用メモリ 272,640 KB
実行使用メモリ 48,256 KB
最終ジャッジ日時 2024-09-17 17:54:08
合計ジャッジ時間 16,556 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
8,320 KB
testcase_01 AC 4 ms
8,064 KB
testcase_02 AC 5 ms
8,320 KB
testcase_03 AC 4 ms
8,192 KB
testcase_04 AC 10 ms
9,216 KB
testcase_05 AC 37 ms
11,136 KB
testcase_06 AC 15 ms
9,088 KB
testcase_07 AC 33 ms
10,752 KB
testcase_08 AC 16 ms
9,600 KB
testcase_09 AC 122 ms
13,824 KB
testcase_10 AC 23 ms
9,088 KB
testcase_11 AC 174 ms
15,360 KB
testcase_12 AC 25 ms
9,216 KB
testcase_13 AC 5 ms
8,448 KB
testcase_14 AC 9 ms
8,576 KB
testcase_15 AC 13 ms
8,960 KB
testcase_16 AC 5 ms
8,448 KB
testcase_17 AC 8 ms
8,704 KB
testcase_18 AC 78 ms
28,416 KB
testcase_19 AC 81 ms
28,416 KB
testcase_20 AC 84 ms
28,416 KB
testcase_21 AC 97 ms
45,056 KB
testcase_22 AC 682 ms
25,344 KB
testcase_23 AC 883 ms
26,496 KB
testcase_24 AC 632 ms
31,616 KB
testcase_25 AC 535 ms
31,616 KB
testcase_26 AC 226 ms
31,744 KB
testcase_27 AC 524 ms
33,408 KB
testcase_28 AC 369 ms
32,384 KB
testcase_29 AC 11 ms
8,448 KB
testcase_30 AC 539 ms
33,536 KB
testcase_31 AC 9 ms
8,448 KB
testcase_32 AC 876 ms
44,032 KB
testcase_33 AC 122 ms
43,904 KB
testcase_34 AC 18 ms
9,088 KB
testcase_35 AC 496 ms
29,696 KB
testcase_36 AC 577 ms
29,696 KB
testcase_37 AC 435 ms
29,568 KB
testcase_38 AC 162 ms
48,256 KB
testcase_39 AC 255 ms
44,800 KB
testcase_40 AC 5 ms
8,576 KB
testcase_41 AC 6 ms
8,704 KB
testcase_42 AC 4 ms
8,576 KB
testcase_43 AC 6 ms
8,576 KB
testcase_44 AC 4 ms
8,832 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
//   }
// }
0