글 읽기 - 비트마스크 왜틀릴까요...?

wjddydgns99 4년 전 2

게시판 몇개 없는 반례까지 정상적으로 돌아가는 것 같은데...

어쨰 틀릴까요?

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int a[100000];
int main()
{
	vector<int> v;
	int n; cin >> n;
	for (int i = 0; i < 2 * n - 1; i++) scanf("%d", &a[i]);
	for (int s = 1; s < (1 << (2*n-1)); s++)
	{
		int count = 0;
		for (int i = 0; i < 2*n-1; i++)
		{
			if (s & (1 << i)) count++;
		}
		if (count != n) continue;
		int sum = 0;
		for (int i = 0; i < 2*n-1; i++)
		{
			if (s & (1 << i))
			{
				sum += a[i];
			}
		}
		if (sum % n == 0)
		{
			for (int i = 0; i < 2*n-1; i++)
			{
				if (s & (1 << i))
				{
					v.push_back(a[i]);
				}
			}
			break;
		}
	}
	if (v.size() == 0)
	{
		cout << -1;
		return 0;
	}
	sort(v.begin(),v. end());
	for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
	return 0;
}

ichigaya_arisa 4년 전 2

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0

wjddydgns99 4년 전 0

우선 감사합니다. 근데 왜 안되는 거죠?

전부 0일 경우, n=15인경우까지 되고, 16부터 -1이 뜨는 것 같은데 이유를 못찾겠습니다...

zzapCoder 4년 전 2

for 문에 s < (1 << (2*n-1)) 를 쓰셨네요. int 자료형에 쉬프트 연산을 이렇게 쓰면 뭔가 이상해지겠죠?

wjddydgns99 4년 전 1

아... N<=500이니깐 2*N-1<=999 이고 비트마스크 쓰면 뭐 대충 2^1000 까지니깐 int나 long long으로 못받아서 문제라는 건가요?

다른 방법으로 접근해야 하나 보네요....

감사합니다...ㅎㅎ 범위 자세히 못봤네요...

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

문제

문제

출처

ICPC

비트마스크 왜틀릴까요...?

wjddydgns99 4년 전 2

ichigaya_arisa 4년 전 2

wjddydgns99 4년 전 0

zzapCoder 4년 전 2

wjddydgns99 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말