oj.uz

Submission #839504

# Submission time Handle Problem Language Result Execution time Memory
839504 2023-08-30T08:21:12 Z _Avocado_ Intercastellar (JOI22_ho_t1) C++14
0 / 100
 16 ms 5452 KB 
#include <bits/stdc++.h>
#define int int64_t
using namespace std;

vector<int>prefix;

int solve(int k, int l, int r){
	if(l == r) return l;
	
	int m = (l+r)/2;
	
	if(prefix[m] - prefix[l-1] < k){
		k -= prefix[m];
		return solve(k, m+1, r);
	}
	return solve(k, l, m);
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	
	int n; cin>>n;
	
	vector<int>v(n);
	for(auto&u: v) cin>>u;
	
	vector<int>two(n);
	prefix.assign(n+1, 0);
	
	for(int i = 0; i<n; ++i){
		int a = v[i];
		int cur = 1;
		
		while(a % 2 == 0){
			a /= 2;
			cur *= 2;
		}
		
		two[i] = cur;
		prefix[i+1] = cur;
	}
	
	for(int i = 1; i<=n; ++i){
		prefix[i] += prefix[i-1];
	}
	
	int q; cin>>q;
	
	for(int i = 0; i<q; ++i){
		int a; cin>>a;
		int index = solve(a, 1, n);
		
		//cout<<"index "<<index<<endl;
		
		cout<<v[index-1]/two[index-1]<<'\n';
	}
	
	cout<<'\n';
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 16 ms 5452 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 16 ms 5452 KB Output isn't correct
4 Halted 0 ms 0 KB -