Submission #534080

#	Time	Username	Problem	Language	Result	Execution time	Memory
534080		PikaQ	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	97 ms	7612 KiB

Main

#include<bits/stdc++.h>
#define forn(i,n) for(int i = 0;i < (n);i++)
#define Forn(i,n) for(int i = 1;i <= (n);i++)
#define all(p) p.begin(),p.end()
#define pb push_back
#define F first
#define S second
#define rz resize
#define sz(x) x.size()
#define int long long
#define vi vector<int>
#define pii pair<int,int>
using namespace std;
const int N = 2e5+9;
int n;

pii broke(int x){
	int cnt = 1;
	while(x % 2 == 0){
		x /= 2;
		cnt *= 2;
	}
	return (pii){x,cnt};
}

void solve(){
	cin >> n;
	vi a(n);
	forn(i,n) cin >> a[i];
	int q;
	vector<pii> b(n+1);
	Forn(i,n){
		b[i] = broke(a[i-1]);
	}
	Forn(i,n){
		if(i) b[i].S += b[i-1].S;
	}
	cin >> q;
	while(q--){
		int c;
		cin >> c;
	  	int lo = 0,hi = n;
		while(lo != hi-1){
			int mid = (lo + hi)/2;
			if(b[mid].S < c) lo = mid;
			else hi = mid;
		}	
		cout << b[lo + 1].F << '\n';
	}
}
signed main(){
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(0);
	solve();
	return 0;
}

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