QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#376457 | #2529. Needle | FOY# | WA | 69ms | 56496kb | C++17 | 2.0kb | 2024-04-04 10:23:15 | 2024-04-04 10:23:15 |
Judging History
answer
#pragma gcc optimize "Ofast"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const ll MIN = 30000;
const ll M = (1<<17) - 1;
typedef complex<double> C;
typedef vector<double> vd;
void fft(vector<C>& a) {
int n = sz(a), L = 31 - __builtin_clz(n);
static vector<complex<long double>> R(2, 1);
static vector<C> rt(2, 1); // (^ 10% faster if double)
for (static int k = 2; k < n; k *= 2) {
R.resize(n); rt.resize(n);
auto x = polar(1.0L, acos(-1.0L) / k);
rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
}
vi rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled) /// include-line
auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k]; /// exclude-line
C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]); /// exclude-line
a[i + j + k] = a[i + j] - z;
a[i + j] += z;
}
}
vd conv(const vd& a, const vd& b) {
if (a.empty() || b.empty()) return {};
vd res(sz(a) + sz(b) - 1);
int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
vector<C> in(n), out(n);
copy(all(a), begin(in));
rep(i,0,sz(b)) in[i].imag(b[i]);
fft(in);
for (C& x : in) x *= x;
rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
fft(out);
rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
vector<vd> c(3, vd(M + 1));
for (ll i = 0; i < 3; i++) {
ll n, x;
cin >> n;
for (ll j = 0; j < n; j++) {
cin >> x;
x += MIN;
if (i == 1) {
c[i][M - 2*x] = 1.0;
} else {
c[i][x] = 1.0;
}
}
}
vd r = conv(c[0], c[1]);
r = conv(r, c[2]);
cout << round(abs(r[M])) << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 62ms
memory: 56420kb
input:
100 -71 -146 -137 -184 -174 -88 -43 -169 -126 -48 -68 -20 -78 -57 -191 -138 -70 -147 -103 -150 -152 -79 -156 -49 -22 -151 -31 -19 -10 -91 -194 -109 -148 -157 -7 -154 -26 -144 -53 -140 -122 -145 -38 -56 -8 -188 -123 -117 -11 -142 -61 -84 -120 -33 -89 -171 -105 -59 -60 -130 -114 -36 -82 -12 -177 -13 -...
output:
1223
result:
ok single line: '1223'
Test #2:
score: 0
Accepted
time: 57ms
memory: 56492kb
input:
100 -40 -78 -88 -81 -14 -47 -9 28 -62 86 61 71 -95 62 97 80 -8 -44 -52 76 13 14 -93 43 23 -21 -37 -33 -85 -29 16 -39 45 48 77 -49 -67 32 -83 83 36 -28 -87 -86 -76 -5 -46 -80 -4 58 -66 9 10 26 -45 -16 56 -50 40 -65 57 -89 30 92 -79 93 73 8 85 24 46 -75 96 29 -1 -100 79 12 -12 -10 -69 -20 -48 -71 20 -...
output:
437
result:
ok single line: '437'
Test #3:
score: 0
Accepted
time: 64ms
memory: 56496kb
input:
1000 -5991 -3571 5600 -1127 -3420 -4551 752 669 -9030 -5885 -639 6593 -9144 5008 -92 -4900 4506 5240 1748 149 2294 -1975 -6329 7565 9076 8683 3153 4918 15 -4742 -3638 -2162 -3860 -3844 -8760 2094 8695 8260 4665 -5955 423 6676 7960 6441 -5415 -9091 -5921 9389 -527 -9979 -5294 7531 410 -6793 -9058 -25...
output:
499098
result:
ok single line: '499098'
Test #4:
score: -100
Wrong Answer
time: 69ms
memory: 56332kb
input:
10000 -24873 -11800 -15593 -18587 -29660 -26233 -16281 -23195 -20826 -27156 -15462 -14208 -12640 -18171 -19519 -13893 -23308 -12651 -14770 -11127 -20175 -22273 -28433 -15971 -14060 -26144 -12100 -16728 -28356 -24547 -16091 -13456 -14096 -10086 -27453 -28189 -21443 -16262 -16073 -25642 -22251 -13011 ...
output:
2.50044e+07
result:
wrong answer 1st lines differ - expected: '25004378', found: '2.50044e+07'