제출 #1197173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197173		vtnoo	Intercastellar (JOI22_ho_t1)	C++20	100 / 100	177 ms	8684 KiB

Main

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <set>

#define pb push_back
#define snd second
#define fst first
#define forn(i,n) for(int i=0;i<n;++i)
#define forsn(i,s,n) for(int i=s; i<n; ++i)
#define all(x) x.begin(), x.end()
#define imp(x) for(auto __:x)cout<<__<<" "; cout<<endl;
#define sz(c) int((c).size())

using namespace std;

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;

int main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;cin>>n;
	vi A(n);
	forn(i,n)cin>>A[i];
	int Q;cin>>Q;
	vi X(Q);
	forn(i,Q)cin>>X[i];
	vector<ii> pref(n);
	auto descomponer=[&](ll x)->ii{
		ll cnt=1;
		while(x%2==0){
			x/=2;
			cnt*=2;
		}
		return {x,cnt};
	};
	forn(i,n){
		pref[i]=descomponer(A[i]);
	}
	//cout<<"==========="<<endl;
	//forn(i,n){
		//cout<<"( "<<pref[i].fst<<" "<<pref[i].snd<<") ";
	//}
	forsn(i,1,n){
		pref[i].snd+=pref[i-1].snd;
	}
	forn(i,Q){
		ll l=-1, r=n;
		while(r-l>1){
			ll m=(r+l)/2;
			if(pref[m].snd<X[i]){
				l=m;
			}else r=m;
		}
		cout<<pref[r].fst<<endl;
	}
}	

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