글 읽기 - 29%에서 틀렸습니다가 뜹니다.

bansh123 3년 전 0

밋인더 미들 사용했고, 사전순으로 젤 앞선거로 출력하기 위해 차이의 크기가 동일 한 경우에는 사전순으로 비교하고 앞서는 경우에만 업데이트 하도록 했습니다. 제 생각에는 잘 돌아갈 것 같은데.. 무엇때문에 틀리는지 모르겠습니다.

혹시 반례나 오류좀 알려주실 수 있을까요??

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std;
long long A[36];
long long B[36];
int C[36];
int D[36];
long long* L;
long long* R;
class ST
{
public:
	long long val;
	int I;
};
bool cmp(const ST& p1, const ST& p2)
{
	return (p1.val < p2.val);
}
vector <ST> LM[19];
vector <ST> RM[19];
bool compare(int a,int b,int c,int x,int y,int z,int N)
{
	int i1 = LM[a][b].I; int j1 = RM[N / 2 - a][c].I;
	int i2 = LM[x][y].I; int j2 = RM[N / 2 - x][z].I;
	if (i1 > i2)
	{
		return true;
	}
	else if (i1 == i2)
	{
		for (int i = 0; i < N / 2; i++)
		{
			if (j1 % 2 > j2 % 2)
			{
				return true;
			}
			else if (j1 % 2 == j2 % 2)
			{
				j1 /= 2;
				j2 /= 2;
				continue;
			}
			else
			{
				return false;
			}
		}
	}
	else
	{
		return false;
	}
	return true;
}
void LDFS(int N, int idx, int level)
{
	if (idx * 2 >= (int)(pow(2, N / 2 + 1) + 0.5))
	{
		return;
	}
	L[idx * 2] = L[idx] - B[level];
	LDFS(N, idx * 2,level +1);
	L[idx * 2 + 1] = L[idx] + A[level];
	LDFS(N, idx * 2 + 1,level +1);
}
void RDFS(int N, int idx, int level)
{
	if (idx * 2 >= (int)(pow(2, N / 2 + 1) + 0.5))
	{
		return;
	}
	R[idx * 2] = R[idx] - B[N-1-level];
	RDFS(N, idx * 2, level + 1);
	R[idx * 2 + 1] = R[idx] + A[N - 1 - level];
	RDFS(N, idx * 2 + 1, level + 1);
}
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];
	for (int i = 0; i < N; i++)
		cin >> B[i];
	L = new long long[(int)(pow(2, N / 2 + 1) + 0.5)];
	R = new long long[(int)(pow(2, N / 2 + 1) + 0.5)];
	L[1] = 0;
	R[1] = 0;
	LDFS(N, 1, 0);
	RDFS(N, 1, 0);
	for (int i = (int)(pow(2, N / 2)+0.5); i < (int)(pow(2, N / 2 + 1)+0.5); i++)
	{
		int cnt = 0;
		int temp = i;
		for (int j = 0; j < N / 2; j++)
		{
			if (temp % 2 == 0)
			{
				cnt++;
			}
			temp /= 2;
		}
		ST myst1 = { L[i],i };
		ST myst2 = { R[i],i };
		LM[cnt].push_back(myst1);
		RM[cnt].push_back(myst2);
	}
	for (int i = 0; i <= N / 2; i++)
	{
		sort(LM[i].begin(), LM[i].end(),cmp);
		sort(RM[i].begin(), RM[i].end(),cmp);
	}
	int a, b, c;
	long long comp = LLONG_MAX - 1;
	for (int i =0; i <=N/2 ; i++)
	{
		for (int j = 0; j < LM[i].size(); j++)
		{
			int first = 0; int last = RM[N / 2 - i].size();
			int mid = RM[N / 2 - i].size() / 2;
			while (1)
			{
				if (last-1==first)
				{
					mid = first;
					break;
				}
				if (first == last)
				{
					mid = last - 1;
					break;
				}
				if (RM[N / 2 - i][mid].val > -1 * LM[i][j].val)
				{
					last = mid;

					mid = (last + first) / 2;
				}
				else if (RM[N / 2 - i][mid].val < -1 * LM[i][j].val)
				{
					first = mid + 1;

					mid = (last + first) / 2;
				}
				else
				{
					break;
				}
			}
			if (mid > 0)
			{
				if (abs(RM[N / 2 - i][mid - 1].val + LM[i][j].val) < comp)
				{
					comp = abs(RM[N / 2 - i][mid - 1].val + LM[i][j].val);
					a = i; b = j; c = mid - 1;
				}
				else if (abs(RM[N / 2 - i][mid - 1].val + LM[i][j].val) == comp)
				{
					if (!compare(a, b, c, i, j, mid - 1, N))
					{
						comp = abs(RM[N / 2 - i][mid - 1].val + LM[i][j].val);
						a = i; b = j; c = mid - 1;
					}
				}
			}
			if(mid>=0&&mid<= RM[N / 2 - i].size() - 1)
			{
				if (abs(RM[N / 2 - i][mid].val + LM[i][j].val) < comp)
				{
					comp = abs(RM[N / 2 - i][mid].val + LM[i][j].val);
					a = i; b = j; c = mid;
				}
				else if (abs(RM[N / 2 - i][mid].val + LM[i][j].val) == comp)
				{
					if (!compare(a, b, c, i, j, mid, N))
					{
						comp = abs(RM[N / 2 - i][mid].val + LM[i][j].val);
						a = i; b = j; c = mid;
					}
				}
			}
			if (mid < RM[N / 2 - i].size() - 1)
			{
				if (abs(RM[N / 2 - i][mid + 1].val + LM[i][j].val) < comp)
				{
					comp = abs(RM[N / 2 - i][mid + 1].val + LM[i][j].val);
					a = i; b = j; c = mid + 1;
				}
				else if (abs(RM[N / 2 - i][mid + 1].val + LM[i][j].val) == comp)
				{
					if (!compare(a, b, c, i, j, mid + 1, N))
					{
						comp = abs(RM[N / 2 - i][mid + 1].val + LM[i][j].val);
						a = i; b = j; c = mid + 1;
					}
				}
			}
		}
	}
	int Li = LM[a][b].I; int Ri = RM[N / 2 - a][c].I;
	for (int i = 0; i < N / 2; i++)
	{
		if (Li % 2 == 1)
			D[N / 2 - 1 - i] = 1;
		else
			D[N / 2 - 1 - i] = 2;
		Li /= 2;
		if (Ri % 2 == 1)
			D[N / 2 + i] = 1;
		else
			D[N / 2 +i] = 2;
		Ri /= 2;
	}
	for (int i = 0; i < N; i++)
		cout << D[i] << " ";
}

bansh123 3년 전 1

자문자답합니다. 차이가 같은경우가 여러개 있는 상황을 제대로 처리를 못했었네요!

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

문제

문제

출처

ICPC

29%에서 틀렸습니다가 뜹니다.

bansh123 3년 전 0

bansh123 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말