oj.uz

Submission #534079

# Submission time Handle Problem Language Result Execution time Memory
534079 2022-03-08T00:32:38 Z PikaQ Intercastellar (JOI22_ho_t1) C++17
0 / 100
 2000 ms 204 KB 
#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]);
	}
	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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -