Submission #864395

#	Time	Username	Problem	Language	Result	Execution time	Memory
864395		NotLinux	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	1694 ms	56952 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 7;
int n,arr[N];
map < int , int > dp;
int calc(int x){
	if(x & 1)return 1;
	else if(dp.count(x))return dp[x];
	else return dp[x] = calc(x/2) * 2;
}
void search(int len ,int cur , int tar){
	if(len & 1){
		cout << len << endl;
	}
	else if((calc(len/2) + cur) < tar){//sağ tarafa
		search(len/2 , cur + calc(len/2) , tar);
	}
	else{//sol tarafa
		search(len/2 , cur + calc(len/2) , tar);
	}
}
void solve(){
	cin >> n;
	for(int i = 0;i<n;i++)cin >> arr[i];
	int pre[n+1];
	memset(pre , 0, sizeof(pre));
	for(int i = 0;i<n;i++){
		pre[i+1] = pre[i] + calc(arr[i]);
	}
	int q;cin >> q;
	while(q--){
		int x;cin >> x;
		int l = 0 , r = n;
		while(l < r){
			int mid = (l+r)/2;
			if(pre[mid] >= x)r = mid;
			else l = mid+1;
		}
		l--;//küçük olan son yer
		search(arr[l] , pre[l-1] , x);
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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