B. Worms Solution | Binary Search | Codeforces Round 271 (Div. 2)
Raunit Verma - in Codeforces
Views: 2
It is lunch time for Mole. His friend, Marmot, prepared him a nice game for lunch. Marmot brought Mole n ordered piles of worms such that i-th pile contains ai worms. He labeled all these worms with consecutive integers: worms in first pile are labeled with numbers 1 to a1, worms in second pile are labeled with numbers a1 + 1 to a1 + a2 and so on. See the example for a better understanding. Mole can't eat all the worms (Marmot brought a lot) and, as we all know, Mole is blind, so Marmot tells him the labels of the best juicy worms. Marmot will only give Mole a worm if Mole says correctly in which pile this worm is contained. Poor Mole asks for your help. For all juicy worms said by Marmot, tell Mole the correct answers.
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
int n;
cin>>n;
vector<int> worms(n);
for(int i = 0; i < n; i++){
cin>>worms[i];
}
int m;
cin>>m;
vector<int> queries(m);
for(int i = 0; i < m; i++){
cin>>queries[i];
}
vector<int> prefix_sum(n);
prefix_sum[0] = worms[0];
for(int i = 1; i < n; i++){
prefix_sum[i] = prefix_sum[i - 1] + worms[i];
}
for(int i = 0; i < m; i++){
int query = queries[i];
auto idx = lower_bound(prefix_sum.begin(), prefix_sum.end(), query) - prefix_sum.begin() + 1;
cout<<idx<<endl;
}
return 0;
}TagscodeforcesB. WormsCodeforces Round 271 (Div. 2)
Raunit Verma
Technical Writer at CodingKaro
Share this on
