Submission #1086194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086194		I_am_Polish_Girl	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	65 ms	12480 KiB

Main

//#pragma target("arch=icelake-server")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack> 
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;

#define int long long

typedef long long ll;
typedef long double ld;

int log_ = 11;
int inf = 4000000007000000007;

long long mod = 1000000007;

int p = 499;

int NADIYA = 39;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n;
	cin >> n;

	vector <int> a(n);

	for (int i = 0; i < n; i++)
		cin >> a[i];

	vector <pair <int, int>> vp;

	for (int i = 0; i < n; i++)
	{
		int c = 1;

		while (a[i] % (c*2) == 0)
			c *= 2;

		vp.push_back({ c , a[i] / c });
	}

	vector <int> pref(n);
	int p = 0;
	
	for (int i = 0; i < n; i++)
	{
		p += vp[i].first;

		pref[i] = p;
	}

	int q;
	cin >> q;
	
	while (q--)
	{
		int ind;
		cin >> ind;

		int l = lower_bound(pref.begin(), pref.end(), ind) - pref.begin();

		//cerr << "R:";
		cout << vp[l].second << "\n";
	}
}

/*5
1 2 1
2 3 1
2 4 1
1 5 4
*/

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