Submission #742015

#	Time	Username	Problem	Language	Result	Execution time	Memory
742015		MODDI	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	446 ms	15972 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, q;
vi arr, two;
int main(){
	cin>>n;
	arr.resize(n);
	two.resize(n);
	for(int i = 0; i < n; i++)	cin>>arr[i];
	vector<pll> segments;
	vl val;
	ll last = -1;
//	reverse(arr.begin(), arr.end());
	for(int i = 0; i < n; i++){
		ll x = arr[i];
		two[i]=1;
		while(x%2 == 0){
			two[i]*=2;
			x/=2;
		}
		segments.pb(mp(last+1, last + two[i]));
		val.pb(x);
		last += two[i];
	}
	ll pref[n];
	pref[0] = segments[0].second + 1;
	for(int i = 1; i < n; i++)
		pref[i] = pref[i-1] + segments[i].second - segments[i].first+1;
	int q;
	cin>>q;
	while(q--)
	{
		ll x;
		cin>>x;
		int l = 0, r = n-1, pos;
		while(l <= r){
			int mid = l + (r-l)/2;
			if(pref[mid] >= x){
				pos = mid;
				r = mid - 1;
			}
			else
				l = mid+1;
		}
		cout<<val[pos]<<endl;
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:52:16: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |   cout<<val[pos]<<endl;
      |                ^

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40