白駿1920号:水を探しています

リンク:https://www.acmicpc.net/problem/1920

問題を読む

Nまでの並びがあります.Xという整数が存在するかどうかを見つけなければなりません.
最初に配列に入れたときに、この木に入れて探索してみるとちょうど良いです.

コード#コード#

Out Of Bounds:右側のノードに積み重ね続けたら?ノードの数は100000個ですが、配列のサイズは287100000+22*100000+2287100000+2でなければなりません.

#include<iostream>
using namespace std;

int arr[100001]{ 0, };
bool full[100001]{ false, };

int main() {
	int N, elem, tmp;
	cin >> N;
    
	for (int i = 0; i < N; i++) {
		cin >> elem;
		tmp = 0;
		while (full[tmp] == true){
			if (arr[tmp] < elem)
				tmp = (2 * tmp) + 2;
			else
				tmp = (2 * tmp) + 1;
		}
		arr[tmp] = elem;
		full[tmp] = true;
	}


	cin >> N;
	for (int j = 0; j < N; j++) {
		cin >> elem;
		tmp = 0;
		while (full[tmp] == true && arr[tmp] != elem) {
			if (arr[tmp] < elem)
				tmp = (2 * tmp) + 2;
			else
				tmp = (2 * tmp) + 1;
		}
		if (arr[tmp] == elem)
			cout << 1 << "\n";
		else
			cout << 0 << "\n";
	}

	return 0;
}

簡単なstructを作成すると->ポインタ未整理エラー

アルゴリズムライブラリのsortを借りる

#include<iostream>
#include<algorithm>
using namespace std;

int arr[100001];
int main() {
	cin.tie(NULL);
	int N, M, elem;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
    
	bool check = false;
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> elem;
		int start = 0, end = N - 1, mid;
		while (start <= end){
			mid = (start + end) / 2;
			if (arr[mid] < elem) {
				start = mid+1;
			}
			else if(arr[mid] > elem){
				end = mid-1;
			}
			else {
				check = true;
				break;
			}
		}
		if (check) {
			cout << "1\n";
			check = false;
		}
		else
			cout << "0\n";
	}
	return 0;
}

ぶんせき

残念ながらなぜか最初のオフサイドを逃してしまいました最後に、while (start <= end)に条件が設定されている場合、midが設定されていなくても、start<=endが設定されていれば問題はない.
そして確認したまた忘れた.

if (check) {
	cout << "1\n";
	check = false;
}