QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376457#2529. NeedleFOY#WA 69ms56496kbC++172.0kb2024-04-04 10:23:152024-04-04 10:23:15

Judging History

This is the latest submission verdict.

  • [2024-04-04 10:23:15]
  • Judged
  • Verdict: WA
  • Time: 69ms
  • Memory: 56496kb
  • [2024-04-04 10:23:15]
  • Submitted

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'