From 9e28e4c7b67c54229df11d355047ac8a88ea1817 Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sun, 15 Dec 2019 15:09:13 +0700 Subject: Normalize pathname --- ntu/keba2.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) create mode 100644 ntu/keba2.c (limited to 'ntu/keba2.c') diff --git a/ntu/keba2.c b/ntu/keba2.c new file mode 100644 index 0000000..d9316fd --- /dev/null +++ b/ntu/keba2.c @@ -0,0 +1,49 @@ +#include +#include + +int cmp(const void *x, const void *y) +{ + return *(long long *) x - *(long long *) y; +} + +int main() +{ + short n, i; + long b; + scanf("%hd %ld", &n, &b); + long long *s = malloc(n * 8); + for (i = 0; i < n; i++) + scanf("%lld", &s[i]); + + qsort(s, n, 8, cmp); + + short m = 0, hist[10000] = {1}; + long long a[10000]; + a[0] = s[0]; + for (i = 1; i < n; i++) { + if (s[i] != a[m]) { + m++; + a[m] = s[i]; + } + hist[m]++; + } + m++; + + long val = 0; + long long foo; + void *p; + for (i = 0; i < m; i++) { + foo = b - a[i]; + if (foo == a[i]) + val += hist[i] * (hist[i] - 1) / 2; + if (foo <= a[i]) + break; + p = bsearch(&foo, a, m, 8, cmp); + if (p != NULL) + val += hist[i] * hist[(long long *) p - a]; + } + + printf("%ld\n", val); + + return 0; +} -- cgit 1.4.1