結果
問題 | No.896 友達以上恋人未満 |
ユーザー | LayCurse |
提出日時 | 2019-09-28 09:09:09 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 536 ms / 3,500 ms |
コード長 | 4,714 bytes |
コンパイル時間 | 2,675 ms |
コンパイル使用メモリ | 215,804 KB |
実行使用メモリ | 85,888 KB |
最終ジャッジ日時 | 2024-10-01 13:17:02 |
合計ジャッジ時間 | 4,734 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 157 ms
37,504 KB |
testcase_06 | AC | 402 ms
37,504 KB |
testcase_07 | AC | 157 ms
37,504 KB |
testcase_08 | AC | 159 ms
37,504 KB |
testcase_09 | AC | 349 ms
71,296 KB |
testcase_10 | AC | 536 ms
85,888 KB |
ソースコード
#pragma GCC optimize ("Ofast") #include<bits/stdc++.h> using namespace std; void *wmem; char memarr[96000000]; template<class S, class T> inline S min_L(S a,T b){ return a<=b?a:b; } 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); } 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 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'); } } int Prime_L(int N, int res[], void *mem=wmem){ int i; int a; int b; int sz = 1; const int r = 23000; bool *isprime; int *sf; int ss = 1; walloc1d(&isprime, r, &mem); walloc1d(&sf, r, &mem); isprime = (bool*)mem; sf = (int*)(isprime + r); N /= 2; res[0] = 2; b =min_L(r, N); for(i=(1);i<(b);i++){ isprime[i] = 1; } for(i=(1);i<(b);i++){ if(isprime[i]){ res[sz++] = 2*i+1; sf[ss] = 2*i*(i+1); if(sf[ss] < N){ while(sf[ss] < r){ isprime[sf[ss]] = 0; sf[ss] += res[ss]; } ss++; } } } for(a=r; a<N; a+=r){ b =min_L(a + r, N); isprime -= r; for(i=(a);i<(b);i++){ isprime[i] = 1; } for(i=(1);i<(ss);i++){ while(sf[i] < b){ isprime[sf[i]] = 0; sf[i] += res[i]; } } for(i=(a);i<(b);i++){ if(isprime[i]){ res[sz++] = 2*i+1; } } } return sz; } int N; int M; int mulX; int addX; int mulY; int addY; int MOD; int X[1000]; int Y[1000]; int A[1000]; int B[1000]; long long z[16777216]; int ps; int p[1077871]; long long res[1000]; long long res2; int main(){ int i, k; wmem = memarr; unsigned long long x; unsigned long long y; unsigned long long a; unsigned long long b; unsigned long long mm; rd(M); rd(N); rd(mulX); rd(addX); rd(mulY); rd(addY); rd(MOD); { int Lj4PdHRW; for(Lj4PdHRW=(0);Lj4PdHRW<(M);Lj4PdHRW++){ rd(X[Lj4PdHRW]); } } { int KL2GvlyY; for(KL2GvlyY=(0);KL2GvlyY<(M);KL2GvlyY++){ rd(Y[KL2GvlyY]); } } { int Q5VJL1cS; for(Q5VJL1cS=(0);Q5VJL1cS<(M);Q5VJL1cS++){ rd(A[Q5VJL1cS]); } } { int e98WHCEY; for(e98WHCEY=(0);e98WHCEY<(M);e98WHCEY++){ rd(B[e98WHCEY]); } } ps =Prime_L(MOD, p); for(i=(0);i<(M);i++){ z[X[i]] += Y[i]; } x = X[M-1]; y = Y[M-1]; mm = MOD - 1; int cTE1_r3A = N; for(i=(M);i<(cTE1_r3A);i++){ x = (x * mulX + addX) & mm; y = (y * mulY + addY) & mm; z[x] += y; } for(k=(0);k<(ps);k++){ for(i=(MOD-1)/p[k]; i; i--){ z[i] += z[i * p[k]]; } } for(i=(0);i<(M);i++){ if((long long)A[i]*B[i] < MOD){ res2 ^= res[i] = z[A[i]]- z[A[i]*B[i]]; } else{ res2 ^= res[i] = z[A[i]]; } } a = A[M-1]; b = B[M-1]; for(i=(M);i<(N);i++){ a = ((a * mulX + addX + mm) & mm) + 1; b = ((b * mulY + addY + mm) & mm) + 1; if(a*b < MOD){ res2 ^= z[a]-z[a*b]; } else{ res2 ^= z[a]; } } { int RZTsC2BF; for(RZTsC2BF=(0);RZTsC2BF<(M);RZTsC2BF++){ wt_L(res[RZTsC2BF]); wt_L('\n'); } } wt_L(res2); wt_L('\n'); return 0; } // cLay varsion 20190925-1 // --- original code --- // int N, M, mulX, addX, mulY, addY, MOD; // int X[1000], Y[1000], A[1000], B[1000]; // ll z[16777216]; // int ps, p[1077871]; // ll res[1000], res2; // // { // ull x, y, a, b, mm; // // rd(M,N,mulX,addX,mulY,addY,MOD); // rd(X(M),Y(M),A(M),B(M)); // ps = Prime(MOD, p); // // rep(i,M) z[X[i]] += Y[i]; // x = X[M-1]; // y = Y[M-1]; // mm = MOD - 1; // REP(i,M,N){ // x = (x * mulX + addX) & mm; // y = (y * mulY + addY) & mm; // z[x] += y; // } // // rep(k,ps) for(i=(MOD-1)/p[k]; i; i--) z[i] += z[i * p[k]]; // rep(i,M) res2 ^= res[i] = z[A[i]] if[(ll)A[i]*B[i] < MOD, - z[A[i]*B[i]]]; // // a = A[M-1]; // b = B[M-1]; // rep(i,M,N){ // a = ((a * mulX + addX + mm) & mm) + 1; // b = ((b * mulY + addY + mm) & mm) + 1; // res2 ^= z[a] if[a*b < MOD, -z[a*b]]; // } // // wtLn(res(M), res2); // }