글 읽기 - 부분점수는 나와야 하는데 어디가 문제인지 ㅠㅠ

medic_programmer 7년 전 0

이분탐색으로 가능한 간격 값을 예측한 다음에

우선순위큐와 분할정복으로 주어진 횟수 안에 그 간격이 가능한지 확인하는 식으로 풀었습니다.

알고리즘이 어떻든 채점 방식으로 보면 부분점수는 받아야 하는데 틀렸습니다가 뜨네요 ㅠㅠ 터무니없는 결과가 나오나 봅니다

long long 문제나 사소한 문제인것같은데 코드 한번씩만 봐주시면 감사하겠습니다 ㅠㅠ

#include<stdio.h>
#define M 100001

int n,index[M*4],size=1;
long long m,d[M],cnt,ansd[M],tree[M*4];

void input()
{
	int i;
	scanf("%d%lld",&n,&m);
	for(i=1; i<=n; i++) scanf("%lld",&d[i]);
}

void tree_edit()
{
	int t,i;
	
	while(1){
		if(size>=n) break;
		size*=2;
	}
	
	for(i=size; i<size+n; i++){
		tree[i] = d[i-size+1];
		index[i] = i;
	}
	
	t = size;
	
	while(1){
		t/=2; if(t==0) break;
		for(i=t; i<t*2; i++){
			if(tree[i*2] > tree[i*2+1]){ tree[i] = tree[i*2+1]; index[i] = index[i*2+1]; }
			else{ tree[i] = tree[i*2]; index[i] = index[i*2]; }
		}
	}
}

void renew(int a)
{
	int in = a;
	
	while(1){
		in /= 2; if(in==0) break;
		if(tree[in*2] > tree[in*2+1]) { tree[in] = tree[in*2+1]; index[in] = in*2+1; }
		else { tree[in] = tree[in*2]; index[in] = in*2; }
	}
}

void DQ(int start,int end,long long cha)
{
	int s = start, e = end, in = index[start], i;
	
	long long ans = tree[start];
	
	if(start>=end) return ;
	
	while(1){
		if(ans > tree[s]) { ans = tree[s]; in = index[s]; }
		if(ans > tree[e]) { ans = tree[e]; in = index[e]; }
		if(s%2 == 1) s++;
		if(e%2 == 0) e--;
		if(s > e) break;
		
		s/=2; e/=2;
	}
	
	if(in != end){
		if(tree[in+1] - tree[in] > cha){
			cnt += (tree[in+1] - (tree[in]+cha));
			tree[in+1] = tree[in]+cha;
			renew(in+1);
		}
	}
	
	if(in != start){
		if(tree[in-1] - tree[in] > cha){
			cnt += (tree[in-1] - (tree[in]+cha));
			tree[in-1] = tree[in]+cha;
			renew(in-1);
		}
	}
	
	DQ(start,in-1,cha); DQ(in+1,end,cha);
}

void process()
{
	int i;
	long long low=0,high=1000000001,mid;
	
	for(i=1; i<=n; i++) ansd[i] = d[i];
	
	while(1){
		
		mid = (low + high) / 2;
		//가능한 간격값을 파라매트릭 서치로 찾는다.
		 
		tree_edit();
		cnt = 0;
		DQ(size,size+n-1,mid);
		
		if(cnt <= m){
			//이 간격을 주어진 횟수 이하로 만드는 것이 가능하다면 
			for(i=1; i<=n; i++) ansd[i] = tree[i+size-1];
			high = mid - 1;
		}
		
		else low = mid + 1;
		if(low > high) break;
	}
}

void output()
{
	int i;
	
	for(i=1; i<=n; i++) printf("%lld ",ansd[i]);
	printf("\n");
}

int main()
{
	input();
	process();
	output();
	return 0;
}

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

문제

문제

출처

ICPC

부분점수는 나와야 하는데 어디가 문제인지 ㅠㅠ

medic_programmer 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말