oj.uz

Submission #1000143

# Submission time Handle Problem Language Result Execution time Memory
1000143 2024-06-16T17:42:08 Z THXuan Intercastellar (JOI22_ho_t1) C++14
25 / 100
 36 ms 5716 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;

void solve()
{
	int n; cin >> n;
	vector<ll>a(n + 1),s(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		if (a[i] % 2 == 1) {
			s[i] = s[i - 1] + 1;
		}
		else {
			for (int j = 1; j <= 20; j++) {
				if ((a[i] / (1 << j)) % 2 == 1) {
					a[i] = a[i] / (1 << j);
					s[i] = s[i - 1] + (1 << j);
					break;
				}
			}
		}
	}
	int q; cin >> q;
	while (q--) {
		ll x; cin >> x;
		int lo = 1; int hi = n;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (s[mid] < x)lo = mid + 1;
			else hi = mid;
		}
		cout << a[lo] << "\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 14 ms 4172 KB Output is correct
4 Correct 20 ms 2392 KB Output is correct
5 Correct 35 ms 5460 KB Output is correct
6 Correct 21 ms 4184 KB Output is correct
7 Correct 36 ms 5456 KB Output is correct
8 Correct 36 ms 5716 KB Output is correct

Subtask #2
0 / 35.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 14 ms 4172 KB Output is correct
4 Correct 20 ms 2392 KB Output is correct
5 Correct 35 ms 5460 KB Output is correct
6 Correct 21 ms 4184 KB Output is correct
7 Correct 36 ms 5456 KB Output is correct
8 Correct 36 ms 5716 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -