글 읽기 - 반례가 있을까요?

xtozero 3년 전 0

말단 노드에 1을 채워 놓고 구간 합이 구하려고 하는 위치 k보다 크면 왼쪽 노드로 진행하고 작으면 k 에서 왼쪽 노드의 구간 합을 제외하고 오른쪽 노드로 진행하는 방식으로 구현하였습니다. 반례가 있다면 도움 요청 드립니다.

#include <cmath>
#include <iostream>
#include <vector>

int MaxN = 2'000'001;
int Capacity;
int TreeSize;

void Update( std::vector<int>& node, int n, int value )
{
	n += Capacity;
	node[n] = value;

	for ( int i = ( n >> 1 ); i > 0; i >>= 1 )
	{
		node[i] = node[i << 1] + node[i << 1 | 1];
	}
}

int Kth( const std::vector<int>& node, int k )
{
	int i = 1;

	for ( ; i < Capacity; )
	{
		if ( node[i << 1] >= k )
		{
			i <<= 1;
		}
		else
		{
			k -= node[i << 1];
			i = ( i << 1 | 1 );
		}
	}

	return i - Capacity;
}

int main( )
{
	std::ios::sync_with_stdio( false );
	std::cin.tie( nullptr );
	std::cout.tie( nullptr );

	Capacity = ( 1 << static_cast<int>( std::ceil( log2( MaxN ) ) ) );
	TreeSize = Capacity * 2;

	std::vector<int> node( TreeSize );

	int n = 0;
	std::cin >> n;

	while ( n-- )
	{
		int t = 0;
		int x = 0;
		std::cin >> t >> x;

		if ( t == 1 )
		{
			Update( node, x, 1 );
		}
		else
		{
			int number = Kth( node, x );
			std::cout << number << "\n";
			Update( node, number, 0 );
		}
	}
    
    return 0;
}

xtozero 3년 전 3

스스로 해결하였습니다. 중복 수에 대한 처리를 안했군요.

powerlsj7 1년 전 0

틀린 이유를 몰랐는데 덕분에 중복 수의 입력 부분을 생각할 수 있었네요. 감사합니다.!

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

문제

문제

출처

ICPC

반례가 있을까요?

xtozero 3년 전 0

xtozero 3년 전 3

powerlsj7 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말