-
Notifications
You must be signed in to change notification settings - Fork 0
/
1498.c
75 lines (66 loc) · 1.68 KB
/
1498.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
int cmp(const void *p1, const void *p2) {
return (*(int *)p1 - *(int *)p2);
}
int numSubseq(int* nums, int numsSize, int target){
qsort(nums, numsSize, sizeof(int), cmp);
int i1 = 0, i2 = numsSize - 1, all = numsSize - 1, cur = 1, ans = 0;
// every loop: nums[i1] will be a part of each answer
while (all) {
cur = (cur * 2) % 1000000007;
all --;
}
while (i2 >= i1) {
if (nums[i1] + nums[i2] <= target) {
all = i2 - i1;
ans = (ans + cur) % 1000000007;
i1 ++;
cur = (cur & 1)? (cur + 1000000007) / 2 : cur / 2;
}
else {
i2 --;
cur = (cur & 1)? (cur + 1000000007) / 2 : cur / 2;
}
}
return ans;
}
int main()
{
int num[10001];
int n;
int t;
scanf("%d", &n);
for(int i = 0; i < n; ++i) scnaf("%d", &num[i]);
scanf("%d", &t);
int ans = numSubseq(num, n, t);
printf("%d\n", ans);
return 0;
}
/*
Best Solution
#define MODULUS 1000000007
int twoPowers(int p) {
// printf("... %d\n", p);
int ret = 1;
long long x = 2;
while (p) {
if (p & 1) ret = (ret * x) % MODULUS;
p >>= 1;
x = (x * x) % MODULUS;
}
return ret;
}
int cmpfunc (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int numSubseq(int* nums, int numsSize, int target){
qsort(nums, numsSize, sizeof(int), cmpfunc);
int left = 0, right = numsSize - 1, ret = 0;
while (left <= right) {
if (nums[left] + nums[right] > target) right--;
else ret = (ret + twoPowers(right - left++)) % MODULUS;
}
//printf("%d\n", twoPowers(5));
return ret;
}
*/