結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー | LayCurse |
提出日時 | 2020-02-14 21:36:57 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 4,377 bytes |
コンパイル時間 | 2,809 ms |
コンパイル使用メモリ | 225,972 KB |
実行使用メモリ | 8,960 KB |
最終ジャッジ日時 | 2024-11-16 00:28:33 |
合計ジャッジ時間 | 4,041 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 16 ms
5,248 KB |
testcase_11 | AC | 12 ms
5,504 KB |
testcase_12 | AC | 68 ms
5,760 KB |
testcase_13 | AC | 10 ms
5,248 KB |
testcase_14 | AC | 24 ms
5,248 KB |
testcase_15 | AC | 9 ms
5,248 KB |
testcase_16 | AC | 24 ms
5,760 KB |
testcase_17 | AC | 12 ms
5,248 KB |
testcase_18 | AC | 68 ms
5,888 KB |
testcase_19 | AC | 27 ms
5,248 KB |
testcase_20 | AC | 73 ms
8,960 KB |
ソースコード
#pragma GCC optimize ("Ofast") #include<bits/stdc++.h> using namespace std; 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 T1, class T2> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){ int i; pair<T1, T2> *arr; walloc1d(&arr, N, &mem); for(i=(0);i<(N);i++){ arr[i].first = a[i]; arr[i].second = b[i]; } sort(arr, arr+N); for(i=(0);i<(N);i++){ a[i] = arr[i].first; b[i] = arr[i].second; } } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline void rd(char &c){ int i; for(;;){ i = getchar_unlocked(); if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){ break; } } c = i; } inline int rd(char c[]){ int i; int sz = 0; for(;;){ i = getchar_unlocked(); if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){ break; } } c[sz++] = i; for(;;){ i = getchar_unlocked(); if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){ break; } c[sz++] = i; } c[sz]='\0'; return sz; } inline void wt_L(char a){ putchar_unlocked(a); } 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){ putchar_unlocked('-'); } while(s--){ putchar_unlocked(f[s]+'0'); } } 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 moddw_L(S a, const T b){ a %= b; if(a < 0){ a += b; } return a; } template<class T> void Unique_L(int &N, T A[], int sorted=0){ int i; int k; if(!sorted){ sort(A, A+N); } k = 0; for(i=(0);i<(N);i++){ if(k==0 || A[k-1]!=A[i]){ A[k++] = A[i]; } } N = k; } template<class T, class S> void Unique_L(int &N, T A[], S B[], int sorted=0){ int i; int k = 0; if(!sorted){ sortA_L(N, A, B); } for(i=(0);i<(N);i++){ if(!k || A[k-1]!=A[i]){ A[k] = A[i]; B[k] = B[i]; k++; } else{ B[k-1] += B[i]; } } N=k; } int N; int M; int K; int A[100000]; int B[100000]; char op; map<int,int> mp; int cntA[100000]; int cntB[100000]; int main(){ wmem = memarr; int i; int j; int k; long long res = 0; rd(N); rd(M); rd(K); rd(op); { int Lj4PdHRW; for(Lj4PdHRW=(0);Lj4PdHRW<(M);Lj4PdHRW++){ rd(B[Lj4PdHRW]); } } { int e98WHCEY; for(e98WHCEY=(0);e98WHCEY<(N);e98WHCEY++){ rd(A[e98WHCEY]); } } if(op=='+'){ for(i=(0);i<(N);i++){ mp[A[i]%K]++; } for(i=(0);i<(M);i++){ j =moddw_L((-B[i]),K); if(mp.count(j)){ res += mp[j]; } } } else{ for(i=(0);i<(N);i++){ cntA[i] = 1; } for(i=(0);i<(M);i++){ cntB[i] = 1; } for(i=(0);i<(N);i++){ A[i] =GCD_L(A[i], K); } for(i=(0);i<(M);i++){ B[i] =GCD_L(B[i], K); } Unique_L(N,A,cntA); Unique_L(M,B,cntB); for(i=(0);i<(N);i++){ for(j=(0);j<(M);j++){ if( (long long)A[i]*B[j]%K==0 ){ res += (long long) cntA[i] * cntB[j]; } } } } wt_L(res); wt_L('\n'); return 0; } // cLay varsion 20200214-1 // --- original code --- // int N, M, K, A[1d5], B[1d5]; // char op; // // map<int,int> mp; // int cntA[1d5], cntB[1d5]; // { // int i, j, k; // ll res = 0; // rd(N,M,K,op,B(M),A(N)); // // if(op=='+'){ // rep(i,N) mp[A[i]%K]++; // rep(i,M){ // j = (-B[i]) %% K; // if(mp.count(j)) res += mp[j]; // } // } else { // rep(i,N) cntA[i] = 1; // rep(i,M) cntB[i] = 1; // rep(i,N) A[i] = gcd(A[i], K); // rep(i,M) B[i] = gcd(B[i], K); // Unique(N,A,cntA); // Unique(M,B,cntB); // rep(i,N) rep(j,M) if( (ll)A[i]*B[j]%K==0 ) res += (ll) cntA[i] * cntB[j]; // } // // wt(res); // }