글 읽기 - 평방분할로 풀었는데 틀린부분을 모르겠습니다..

kdr06006 4년 전 1

반례를 도저히 모르겠는데 어느 부분에서 잘못되었는지 알려주시면 감사하겠습니다,,

#include<stdio.h>

const int INF = 1e9 + 1, _size = 1e5 + 1;
int sqrtN, arr[_size];
typedef struct Infor {
	int idx, value;
}I;
I sqrt_arr[(int)1e3 + 1];

inline I min(I a, I b) { return a.value <= b.value ? a : b; }

int sqrt(int N)
{
	double ret = N;
	for (int i = 0; i < 16; i++) {
		ret = ret - (ret * ret - N) / (ret * 2);
	}
	return (int)ret;
}

int main(void)
{
	int N, M;
	scanf("%d", &N);
	sqrtN = sqrt(N);
	for (int i = 0; i <= N / sqrtN; i++) sqrt_arr[i] = { 0,INF };

	arr[0] = INF;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]);
		sqrt_arr[i / sqrtN] = min(sqrt_arr[i / sqrtN], { i,arr[i] });
	}

	scanf("%d", &M);
	int n1, n2, n3;
	while (M--) {
		scanf("%d", &n1);
		if (n1 == 1) {
			scanf("%d %d", &n2, &n3);
			arr[n2] = n3;
			sqrt_arr[n2 / sqrtN] = { 0,INF };
			for (int i = n2 / sqrtN * sqrtN; n2 / sqrtN == i / sqrtN; i++) {
				sqrt_arr[n2 / sqrtN] = min(sqrt_arr[n2 / sqrtN], { i,arr[i] });
			}
		}
		else {
			I res = { 0,INF };
			for (int i = 0; i <= N / sqrtN; i++) {
				res = min(res, sqrt_arr[i]);
			}
			printf("%d\n", res.idx);
		}
	}
}

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

문제

문제

출처

ICPC

평방분할로 풀었는데 틀린부분을 모르겠습니다..

kdr06006 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말