結果

問題 No.15 カタログショッピング
ユーザー mudbdbmudbdb
提出日時 2015-07-12 05:04:29
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 17 ms / 5,000 ms
コード長 3,700 bytes
コンパイル時間 958 ms
コンパイル使用メモリ 27,332 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-22 14:18:31
合計ジャッジ時間 1,541 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 0 ms
4,376 KB
testcase_04 AC 0 ms
4,380 KB
testcase_05 AC 16 ms
4,380 KB
testcase_06 AC 16 ms
4,380 KB
testcase_07 AC 17 ms
4,376 KB
testcase_08 AC 16 ms
4,376 KB
testcase_09 AC 16 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
struct sum {
  int prod;
  int sum;
};
struct prod {
  struct prod *next;
  unsigned int bitfield;
};
int N;
int S;
int *P;
int cmp(const void* a, const void* b)
{
  return (((struct sum*)a)->sum - ((struct sum*)b)->sum);
}
int cmp2(const void* a, const void* b)
{
  return (((struct sum*)b)->sum - ((struct sum*)a)->sum);
}
struct prod *Prod = 0;
void list_in(int prod1, int prod2)
{
  struct prod *new = (struct prod*)malloc(sizeof(struct prod));
  unsigned int bitfield = (prod2 << N/2)|prod1;
  new->bitfield = 0;

  int i;
  for (i=0; i<N; i++) {
    if (bitfield & (1 << i)) {
      new->bitfield |= (1 << (N-1-i));
    }
  }

  struct prod *list = Prod;
  struct prod *hold = 0;
  while (list != 0) {
    if (new->bitfield > list->bitfield) break;
    hold = list;
    list = list->next;
  }
  if (hold == 0) {
    new->next = Prod;
    Prod = new;
  } else {
    new->next = hold->next;
    hold->next = new;
  }
  return;
}
struct prod *list_scan(struct prod *cur)
{
  if (cur == 0) {
    return Prod;
  } else {
    return cur->next;
  }
}
int main()
{
  // 1 <= N <= 31
  scanf("%d", &N);
  scanf("%d", &S);
  P = (int*)malloc(sizeof(int)*N);
  int i;
  for (i=0; i<N; i++) scanf("%d", &(P[i]));

  int list1_n = 1;
  for (i=0; i<N/2; i++) list1_n *=2;
  struct sum *list1 = (struct sum*)malloc(sizeof(struct sum)*list1_n);

  int j, k;
  for (i=0; i<list1_n; i++) {
    list1[i].prod = i;
    list1[i].sum = 0;
    k = i;
    for (j=0; j<N/2; j++) {
      if (k & 1) {
        list1[i].sum += P[j];
        if (S < list1[i].sum) {
          list1[i].sum = S + 1;
          break;
        }
      }
      k >>= 1;
      if (!k) {
        break;
      }
    }
  }

  qsort(list1, list1_n, sizeof(struct sum), cmp);
  for (i=0; i<list1_n; i++) {
    if (list1[i].sum >= S+1) {
      break;
    }
  }
  list1_n = i;

  int list2_n = 1;
  for (i=N/2; i<N; i++) list2_n *=2;
  struct sum *list2 = (struct sum*)malloc(sizeof(struct sum)*list2_n);

  for (i=0; i<list2_n; i++) {
    list2[i].prod = i;
    list2[i].sum = 0;
    k = i;
    for (j=N/2; j<N; j++) {
      if (k & 1) {
        list2[i].sum += P[j];
        if (S < list2[i].sum) {
          list2[i].sum = -1;
          break;
        }
      }
      k >>= 1;
      if (!k) {
        break;
      }
    }
  }

  qsort(list2, list2_n, sizeof(struct sum), cmp2);
  for (i=0; i<list2_n; i++) {
    if (list2[i].sum <= -1) {
      break;
    }
  }
  list2_n = i;

  i = 0;
  j = 0;
  int sum;
  int tmp1;
  int tmp2;
  struct prod *prod;
  while (1) {
    sum = list1[i].sum + list2[j].sum;
    if (sum < S) {
      tmp1 = list1[i].sum;
      do {
        i++;
      } while ((i < list1_n) && (tmp1 == list1[i].sum));
    } else if (sum > S) {
      tmp2 = list2[j].sum;
      do {
        j++; 
      } while ((j < list2_n) && (tmp2 == list2[j].sum));
    } else {
      int jstart = j;
      int jend;
      tmp1 = list1[i].sum;
      tmp2 = list2[j].sum;
      while (1) {
        list_in(list1[i].prod, list2[j].prod);
        j++;
        if ((j >= list2_n) || (tmp2 != list2[j].sum)) {
          jend = j;
          j = jstart;
          i++;
          if ((i >= list1_n) || (tmp1 != list1[i].sum)) {
            j = jend;
            break;
          }
        }
      }
    }
    if (i >= list1_n) break;
    if (j >= list2_n) break;
  }

  int print;
  struct prod *list = list_scan(0);
  while (list != 0) {
    print = 0;
    for (k=0; k<N; k++) {
      if (list->bitfield & (1 << (N-1-k))) {
        if (print == 1) printf(" ");
        printf("%d", k+1);
        if (print == 0) print = 1;
      }
    }
    if (print == 1) printf("\n");
    list = list_scan(list);
  }

  return 0;
}
0