Submission #534098

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
534098	2022-03-08T01:04:16 Z	Wither	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	336 ms	7068 KB

Main

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define INF (ll)(9e18)
#define int long long int
using namespace std;
using ll=long long;
using pii=pair<int,int>;

pii tc (int n){
	int i=1;
	while (n%2==0){
		i*=2;
		n/=2;
	}
	return {i,n};
}





int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int N,Q,temp;
	vector<int> ans;
	cin>>N;
	
	
	int nb[N];
	int ad[N];
	
	for (int i=0;i<N;i++){
		cin>>temp;
		pii tempp=tc(temp);
		
		if (i==0){
			ad[i]=tempp.F;
			nb[i]=tempp.S;
		}
		else{
			ad[i]=ad[i-1]+tempp.F;
			nb[i]=tempp.S;
		}
	}
	
	cin>>Q;
	for (int i=0;i<Q;i++){
		cin>>temp;
		int l=0;
		int r=N-1;
		int m=(l+r)/2;
		
		while (l!=r and ad[m]!=temp){
			if (ad[m]>temp){
				r=m;
			}
			else{
				l=m+1;
			}
			m=(l+r)/2;
		}
		ans.push_back(nb[m]);
	}
	for (int i=0;i<Q;i++){
		cout<<ans[i]<<endl;
	}
	
	
	
		
	
}

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	80 ms	3964 KB	Output is correct
4	Correct	195 ms	3260 KB	Output is correct
5	Correct	291 ms	5556 KB	Output is correct
6	Correct	135 ms	4080 KB	Output is correct
7	Correct	271 ms	5604 KB	Output is correct
8	Correct	299 ms	5568 KB	Output is correct

Subtask #2

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	2 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	2 ms	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	3 ms	332 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	80 ms	3964 KB	Output is correct
4	Correct	195 ms	3260 KB	Output is correct
5	Correct	291 ms	5556 KB	Output is correct
6	Correct	135 ms	4080 KB	Output is correct
7	Correct	271 ms	5604 KB	Output is correct
8	Correct	299 ms	5568 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	2 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	3 ms	332 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	161 ms	3000 KB	Output is correct
24	Correct	149 ms	4088 KB	Output is correct
25	Correct	293 ms	7068 KB	Output is correct
26	Correct	187 ms	3788 KB	Output is correct
27	Correct	145 ms	3776 KB	Output is correct
28	Correct	298 ms	6228 KB	Output is correct
29	Correct	308 ms	5608 KB	Output is correct
30	Correct	214 ms	2816 KB	Output is correct
31	Correct	336 ms	6012 KB	Output is correct