POJ.3977 Subset

1.Problem
http://poj.org/problem?id=3977

2.Idea
Semi enumeration + Binary search

3.Source (WA code)

 struct Item {  
      ll v;  
      int num;  
      bool operator < (const Item &a)const {  
           return v < a.v;  
      }  
 } A[262149], B[262149];  
 ll a[20];  
 ll b[20];  
 int n, n1, n2, N1, N2;  
 void solve()  
 {  
      for (int i = 0; i < N1; i++) {  
           int k = i;  
           int j = 0;  
           int cnt = 0;  
           ll sum = 0;  
           while (k) {  
                sum += a[j];  
                cnt++;  
                j++;  
                k = k >> 1;  
           }  
           A[i].v = sum;  
           A[i].num = cnt;  
      }  
      for (int i = 0; i < N2; i++) {  
           int k = i;  
           int j = 0;  
           int cnt = 0;  
           ll sum = 0;  
           while (k) {  
                sum += b[j];  
                cnt++;  
                j++;  
                k = k >> 1;  
           }  
           B[i].v = sum;  
           B[i].num = cnt;  
      }  
      sort(A, B + N1);  
      sort(B, B + N2);  
      ll retVal = 1LL << 40 , retNum = 0;  
      for (int i = 0; i < N1; i++) {  
           ll tmp = A[i].v;  
           if (tmp < 0) tmp *= -1;  
           if (A[i].num > 0 && tmp < retVal) {  
                retVal = tmp;  
                retNum = A[i].num;  
           }  
      }  
      for (int i = 0; i < N2; i++) {  
           ll tmp = B[i].v;  
           if (tmp < 0) tmp *= -1;  
           if (B[i].num > 0 && tmp < retVal) {  
                retVal = tmp;  
                retNum = B[i].num;  
           }  
      }  
      for (int i = 0; i < N1; i++) {  
           A[i].v *= -1;  
           int ind = lower_bound(B, B + N2, A[i]) - B;  
           A[i].v *= -1;  
           for (int j = ind-2; j < ind + 2; j++) {  
                if (j >= 0 && j < N2) {  
                     ll tmp = A[i].v + B[j].v;  
                     if (tmp < 0) tmp = -tmp;  
                     ll num = A[i].num + B[j].num;  
                     if (num > 0 && tmp < retVal) {  
                          retVal = tmp;  
                          retNum = num;  
                     }  
                }  
           }  
      }  
      for (int i = 0; i < N2; i++) {  
           B[i].v *= -1;  
           int ind = lower_bound(A, A + N2, B[i]) - A;  
           B[i].v *= -1;  
           for (int j = ind - 2; j < ind + 2; j++) {  
                if (j >= 0 && j < N2) {  
                     ll tmp = B[i].v + A[j].v;  
                     if (tmp < 0) tmp = -tmp;  
                     ll num = B[i].num + A[j].num;  
                     if (num > 0 && tmp < retVal) {  
                          retVal = tmp;  
                          retNum = num;  
                     }  
                }  
           }  
      }  
      printf("%lld %lld\n", retVal, retNum);  
 }  
 int main()  
 {  
      while (scanf("%d", &n), n) {  
           if (n == 1) {  
                ll tmp;  
                cin >> tmp;  
                cout << tmp << " " << 1 << endl;  
                continue;  
           }  
           n1 = n / 2;  
           n2 = (n + 1) / 2;  
           N1 = (int)pow(2.0, n2);  
           N2 = (int)pow(2.0, n2);  
           for (int i = 0; i < n1; i++) {  
                scanf("%lld", &a[i]);  
           }  
           for (int i = 0; i < n2; i++) {  
                scanf("%lld", &b[i]);  
           }  
           solve();  
      }  
      return 0;  
 }