結果

問題 No.15 カタログショッピング
ユーザー たこしたこし
提出日時 2015-06-12 19:00:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 2,841 bytes
コンパイル時間 1,074 ms
コンパイル使用メモリ 106,188 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-06 15:52:54
合計ジャッジ時間 1,336 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define INF_MIN 100000000
#define INF 1145141919
#define INF_MAX 2147483647
#define LL_MAX 9223372036854775807
#define EPS 1e-10
#define PI acos(-1)
#define LL long long

using namespace std;

#define MAX_N 31

int N;
LL S;
LL P[MAX_N];

//値,文字列　
typedef pair<LL, LL> PP;

vector<PP> Left, Right;

vector<LL> ans_List;

bool leftBig(LL l1, LL l2){

  for(int i = 0; i < MAX_N; i++){
    if(((l1 >> i) & 1) != ((l2 >> i) & 1)){
      if((l1 >> i) & 1)
	return false;
      else
	return true;
    }
  }

  return false;

}

void mSort(){

  for(int i = 0; i < ans_List.size(); i++){
    for(int j = i+1; j < ans_List.size(); j++){
      if(leftBig(ans_List[i], ans_List[j])){
	//cout << ans_List[i] << " " << ans_List[j] << endl;
	swap(ans_List[i], ans_List[j]);
      }
    }
  }

}

int main(){

  cin >> N >> S;
  for(int i = 0; i < N; i++){
    cin >> P[i];
  }

  //左側半分列挙
  for(int i = 0; i < (1 << N/2); i++){
    
    LL ss = 0;
    LL ret = 0;

    for(int j = 0; j < N/2; j++){
      if((i >> j) & 1){
	ss |= (1 << j);
	ret += P[j];
      }
    }
    
    Left.push_back(PP(ret, ss));

  }

  //右側半分列挙
  for(int i = 0; i < (1 << (N+1)/2); i++){
    
    LL ss = 0;
    LL ret = 0;
    
    for(int j = N/2; j < N; j++){
      if((i >> (j-N/2)) & 1){
	ss |= (1 << j);
	ret += P[j];
      }
    }

    Right.push_back(PP(ret, ss));

  }

  sort(Left.begin(), Left.end());
  sort(Right.begin(), Right.end());

  /* デバッグ
  printf("Left\n");
  for(int i = 0; i < Left.size(); i++){
    printf("%s%lld\n", Left[i].second.c_str(), Left[i].first);
  }
  printf("Right\n");
  for(int i = 0; i < Right.size(); i++){
    printf("%s%lld\n", Right[i].second.c_str(), Right[i].first);
  }
  */

  //にぶたん
  for(int l = 0; l < Left.size(); l++){
    
    LL tmpS = S - Left[l].first;

    int lr = lower_bound(Right.begin(), Right.end(), PP(tmpS,0)) - Right.begin();

    int rr = lower_bound(Right.begin(), Right.end(), PP(tmpS+1,0)) - Right.begin();
    
    while(lr < rr){
      
      ans_List.push_back(Left[l].second | Right[lr].second);

      lr++;

    }

  }

  

  mSort();

  for(int i = 0; i < ans_List.size(); i++){
    
    stringstream ss;
    
    for(int j = 0; j < N; j++){
      if((ans_List[i] >> j) & 1){
	ss << j+1 << " ";
      }
    }

    string ans = ss.str();

    cout << ans.substr(0, ans.length()-1) << endl;

  }

  return 0;

}
0