글 읽기 - 반례부탁드립니다

p_ce1052 3년 전 0

이미 1208의 부분집합의 합 문제에서 AC를 받은 코드를 고쳐서 만들었습니다. 그래서 map에 저장되는 변수들은 틀린 것 같지는 않은데 어디서 틀리는지 도저히 모르겠습니다. 여러 데이터를 넣어봤는데 찾지 못하겠네요

#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> pi;
map<long long,long long>s1,s2;
vector<pi>st1,st2;
vector<long long>psum;

void process(vector<long long>&a,map<long long,long long>&s){ //(x,합이 x인 부분집합의 개수)를 저장. 
	for(int i=0; i<a.size(); i++){
		vector<pair<int,long long> >made;
		made.push_back(make_pair(a[i],1));
		for(auto it = s.begin(); it!=s.end(); it++){
			made.push_back(make_pair(it->first+a[i],it->second));
		}
		for(int j=0; j<made.size(); j++) s[made[j].first]+=made[j].second;
	}	
}
long long bsearch(long long finder){ //finder에 대한 upper bound 
	int l = 0;
	int r = st2.size()-1;
	while(l<=r){
		int mid = (l+r)/2;
		if(st2[mid].first<=finder) l = mid+1;
		else r = mid-1;
	}
	l--;
	if(l<0) return 0;
	else return psum[l];
}
int main(){
	long long n,sum;
	cin>>n>>sum;
	vector<long long>arr(n);
	for(int i=0; i<n; i++) cin>>arr[i];
	vector<long long>arr2;
	for(int i=0; i<n/2; i++){
		arr2.push_back(arr.back());
		arr.pop_back();
	}
    
    //s1에는 처음 절반 배열에 대해 (x, 합이 x인 부분집합의 개수) 가 저장됨.
	//s2에는 뒤의 절반 배열에 대해 (x, 합이 x인 부분집합의 개수) 가 저장됨.  
	process(arr,s1);
	process(arr2,s2);
	
	//이분탐색을 위해 배열에 옮겨담는다. 
	long long ret = 0;
	for(auto it = s1.begin(); it!=s1.end(); it++) st1.push_back(pi(it->first,it->second));
	for(auto it = s2.begin(); it!=s2.end(); it++) st2.push_back(pi(it->first,it->second));
	
	for(int i=0; i<st2.size(); i++){
		if(i==0) psum.push_back(st2[i].second);
		else psum.push_back(st2[i].second+psum.back());
	}
	//앞의 원소만 포함하는 경우 + 앞, 뒤의 원소를 전부 포함하는 경우 
	for(int i=0; i<st1.size(); i++){
		if(st1[i].first<=sum) ret+=st1[i].second*(1+bsearch(sum-st1[i].first));
	}
	
	//뒤의 원소만 포함하는 경우의 수  
	for(int i=0; i<st2.size(); i++){
		if(st2[i].first<=sum) ret+=st2[i].second;
	}
	
	//전체 집합 수 + 공집합  
	cout<<ret+1;
}

YunGoon 3년 전 2

10번 줄에서 pair<int, long long>로 선언하셨는데, int가 오버플로우나지 않을까요?

p_ce1052 3년 전 0

^^7 감사합니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례부탁드립니다

p_ce1052 3년 전 0

YunGoon 3년 전 2

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말