Submission #768830

#	Time	Username	Problem	Language	Result	Execution time	Memory
768830		NintsiChkhaidze	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	298 ms	12292 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define s second
#define f first
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
#define pii pair <int,int>
#define int ll 
using namespace std;

const int N = 2e5 + 5;

int a[N],pr[N];
pii v[N];

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n;
	cin>> n;
	
	for (int i = 1; i <= n; i++)
		cin>>a[i];
		
	int id = 0;
	for (int i= 1; i <= n; i++){
		if (a[i] & 1) {
			v[i] = {1,a[i]};
			continue;
		}
		
		int x = 2;
		for (int j = 1; j <= 50; j++){
			if ((a[i] % (1LL<<j)) == 0){
				x = (1LL<<j);
			}else{
				break;
			}
		}
	
		v[i] = {x,a[i]/x};
	}
	
	for (int i = 1; i <= n; i++){
		pr[i] = pr[i - 1] + v[i].f;
	}
	
	int Q;
	cin>>Q;
	
	while (Q--){
		int x;
		cin>>x;
		
		int l = 1,r = n,res;
		while (l <= r){
			int mid = (l + r)/2;
			if (pr[mid] >= x){
				r = mid - 1;
				res = mid;
			}else{
				l = mid + 1;
			}
		}
		
		cout<<v[res].s<<endl;
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:26:6: warning: unused variable 'id' [-Wunused-variable]
   26 |  int id = 0;
      |      ^~
Main.cpp:4:11: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
    4 | #define s second
      |           ^~~~~~
Main.cpp:56:19: note: 'res' was declared here
   56 |   int l = 1,r = n,res;
      |                   ^~~

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