Submission #531712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531712	2022-03-01T10:20:36 Z	errorgorn	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	345 ms	9156 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,q;
ll arr[200005];
ll cnt[200005];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	rep(x,1,n+1){
		cin>>arr[x];
		cnt[x]=arr[x]&-arr[x];
		arr[x]/=cnt[x];
	}
	
	rep(x,1,n+1) cnt[x]+=cnt[x-1];
	
	ll a;
	cin>>q;
	while (q--){
		cin>>a;
		
		int lo=0,hi=n,mi;
		while (hi-lo>1){
			mi=hi+lo>>1;
			
			if (a<=cnt[mi]) hi=mi;
			else lo=mi;
		}
		
		cout<<arr[hi]<<endl;
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:48:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |    mi=hi+lo>>1;
      |       ~~^~~

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	77 ms	4080 KB	Output is correct
4	Correct	204 ms	2308 KB	Output is correct
5	Correct	326 ms	5508 KB	Output is correct
6	Correct	175 ms	4076 KB	Output is correct
7	Correct	323 ms	5484 KB	Output is correct
8	Correct	290 ms	5604 KB	Output is correct

Subtask #2

35.0 / 35.0

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

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	77 ms	4080 KB	Output is correct
4	Correct	204 ms	2308 KB	Output is correct
5	Correct	326 ms	5508 KB	Output is correct
6	Correct	175 ms	4076 KB	Output is correct
7	Correct	323 ms	5484 KB	Output is correct
8	Correct	290 ms	5604 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	328 KB	Output is correct
19	Correct	2 ms	364 KB	Output is correct
20	Correct	3 ms	468 KB	Output is correct
21	Correct	1 ms	328 KB	Output is correct
22	Correct	2 ms	368 KB	Output is correct
23	Correct	159 ms	3036 KB	Output is correct
24	Correct	124 ms	5188 KB	Output is correct
25	Correct	282 ms	8644 KB	Output is correct
26	Correct	159 ms	5444 KB	Output is correct
27	Correct	129 ms	5464 KB	Output is correct
28	Correct	299 ms	9156 KB	Output is correct
29	Correct	345 ms	8564 KB	Output is correct
30	Correct	234 ms	3636 KB	Output is correct
31	Correct	316 ms	9036 KB	Output is correct