oj.uz

Submission #51807

# Submission time Handle Problem Language Result Execution time Memory
51807 2018-06-21T08:54:52 Z jh05013 씽크스몰 (kriii3_TT) C++17
30 / 30
 7791 ms 263396 KB 
#include <bits/stdc++.h>
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    #ifdef jh
    freopen("input.txt", "r", stdin);
    #endif
}

int SZ = 1, N = 1<<SZ;

int Rev(int x){
    int r = 0;
    for(int i=0; i<SZ; i++) r = r<<1 | (x&1), x>>= 1;
    return r;
}
const long double PI = 3.141592653589793238462643383279502884197169399375105820974;
typedef complex<long double> CD;
typedef vector<CD> VCD;
void FFT(VCD& A, int f){
    CD x, y, z;
    for(int i=0; i<N; i++){
        int j = Rev(i);
        if(i < j) swap(A[i], A[j]);
    }
    for(int i=1; i<N; i<<= 1){
        long double w = PI / i;
        if(f) w = -w;
        CD x(cosl(w), sinl(w));
        for(int j=0; j<N; j+= i<<1){
            CD y(1);
            for(int k=0; k<i; k++){
                CD z = A[i+j+k] * y;
                A[i+j+k] = A[j+k] - z, A[j+k]+= z;
                y*= x;
            }
        }
    }
    if(f) for(int i=0; i<N; i++) A[i]/= N;
}

int main(){OJize();
    int n, m, x; cin>>n>>m;
    while(n+m+2 > N) SZ++, N<<=1;
    VCD A(N), B(N), AR(N), BR(N);
    
    for(int i=0; i<n+1; i++) cin>>x, A[i] = CD(x>>10, x&1023);
    for(int i=0; i<m+1; i++) cin>>x, B[i] = CD(x>>10, x&1023);
    FFT(A, 0); FFT(B, 0);
    for(int i=0; i<N; i++){
        int j = i? N-i : i;
        CD f1 = (A[i] + conj(A[j])) / CD(2, 0), f2 = (A[i] - conj(A[j])) / CD(0, 2),
           f3 = (B[i] + conj(B[j])) / CD(2, 0), f4 = (B[i] - conj(B[j])) / CD(0, 2);
        AR[i] = f1 * (f3 + f4 * CD(0, 1)), BR[i] = f2 * (f3 + f4 * CD(0, 1));
    }
    FFT(AR, 1); FFT(BR, 1);
    ll ans = 0;
    for(int i=0; i<n+m+2; i++){
        ll ar = roundl(real(AR[i])) + 0.01, ai = roundl(imag(AR[i])) + 0.01,
           br = roundl(real(BR[i])) + 0.01, bi = roundl(imag(BR[i])) + 0.01;
        ll res = bi + ((ai + br) << 10) + (ar << 20);
        ans^= res;
    }
    cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 4 ms 720 KB Output is correct
5 Correct 6 ms 744 KB Output is correct
6 Correct 6 ms 776 KB Output is correct
7 Correct 6 ms 856 KB Output is correct
8 Correct 6 ms 856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 4692 KB Output is correct
2 Correct 352 ms 16980 KB Output is correct
3 Correct 352 ms 16980 KB Output is correct
4 Correct 827 ms 33364 KB Output is correct
5 Correct 850 ms 33516 KB Output is correct
6 Correct 813 ms 33516 KB Output is correct
7 Correct 818 ms 33516 KB Output is correct
8 Correct 806 ms 33516 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1689 ms 66404 KB Output is correct
2 Correct 3716 ms 132024 KB Output is correct
3 Correct 3488 ms 132052 KB Output is correct
4 Correct 7439 ms 263276 KB Output is correct
5 Correct 7331 ms 263276 KB Output is correct
6 Correct 7485 ms 263292 KB Output is correct
7 Correct 7791 ms 263396 KB Output is correct
8 Correct 7505 ms 263396 KB Output is correct