글 읽기 - 1044번 맞왜틀

jjang36524 3년 전 0

미트 인 더 미들인데 틀립니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#define int long long
using namespace std;
int N;
int arr[36][2];
vector<pair<int,int>>t;
signed main()
{
	int N;
	cin >> N;
	int i;
	for (i = 0; i < N; i++)
	{
		cin >> arr[i][0];
	}
	for (i = 0; i < N; i++)
	{
		cin >> arr[i][1];
	}
	for (i = 0; i <(1<< (N / 2)); i++)
	{
		int j;
		int r = 0;
		for (j = N/2-1; j >=0; j--)
		{
			if (i & (1 << (N/2-1-j)))
			{
				r += arr[j][1];
			}
			else
				r -= arr[j][0];
		}
		t.push_back({ r,i });
	}
	sort(t.begin(), t.end());
	pair<int, pair<int, int>>ans = { 1LL << 60,{0,0} };
	for (i = 0; i < (1 << ((N+1) / 2)); i++)
	{
		int j;
		int r = 0;
		for (j = N-1; j >=N/2; j--)
		{
			if (i & (1 << (N-j-1)))
			{
				r += arr[j][1];
			}
			else
				r -= arr[j][0];
		}
		int s = lower_bound(t.begin(), t.end(), make_pair( -r,0LL )) - t.begin();
		for (j = s - 3; j <= s + 3; j++)
		{
			if (j < 0 || j >= t.size())
				continue;
			ans = min(ans, { abs(r + t[j].first), {t[j].second,i} });
		}
	}
	for (i = 0; i < N / 2; i++)
	{
		cout << (ans.second.first & (1 << (N/2-1-i))) / (1 << (N/2-1-i))+1  << ' ';
	}
	for (i = N/2; i < N; i++)
	{
		cout << (ans.second.second & (1 << (N-1-i))) / (1 << (N-1-i)) + 1 << ' ';
	}
}

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

문제

문제

출처

ICPC

1044번 맞왜틀

jjang36524 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말