글 읽기 - 반례 질문드립니다.

qktlf789456 3년 전 0

그냥 간단하게 구현해보았습니다.

문제 로직상 오류가없다고 생각하여 통과할줄알았는데 아무리 봐도 오류가보이지않네요... 어떤 반례가 존재할까요?

#include <iostream>

using namespace std;




int num[100001];
int bucket[100001];
int n;

void merge_sort(int start, int last)
{
	if (start >= last)
		return;

	int mid = (start + last) / 2;

	merge_sort(start, mid);
	merge_sort(mid + 1, last);

	int left = start;
	int right = mid + 1;

	int b_idx = start;
	while (left <= mid && right <= last)
	{
		if (num[left] >= num[right])
			bucket[b_idx++] = num[left++];
	
		else
			bucket[b_idx++] = num[right++];
	}

	while(left <= mid)
		bucket[b_idx++] = num[left++];


	while(right <= last)
		bucket[b_idx++] = num[right++];


	for (int i = start; i <= last; i++)
		num[i] = bucket[i];




	
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> num[i];

	merge_sort(0, n - 1);


	char ans = 1;


	int remain=0;
	int cur_minus;
	for (int i = 0; i < n && ans; i++)
	{
		if (remain)
		{
			num[i] -= (3 - remain);

			if (num[i] < 0)
			{
				ans = 0;
				break;
			}
		}


		remain = num[i] % 3;
	}

	if (remain)
		ans = 0;

	if (ans)
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

chainjaxx 1년 전 0

반례입니다.

10 1 1 0 3 5 3 6 1 7 0

expected: YES

received: NO

10 4 6 1 7 0 1 0 9 1 7

expected: YES

received: NO

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

문제

문제

출처

ICPC

반례 질문드립니다.

qktlf789456 3년 전 0

chainjaxx 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말