6640 | 2023. 12. 14 08:57:55 | Huni136 | Zenehallgatás | cpp17 | Elfogadva 50/50 | 104ms | 5844 KiB |
#include <iostream>
#include <map>
#include <vector>
using namespace std;
map<int,int> vlmi;
vector<int> a(100002,1e9);
// int binkeres(int x, int kezd, int veg)
// {
// if(kezd<=veg)
// {
// int kozep=(kezd+veg)/2;
// if(a[kozep]>=x && a[kozep-1]<x)
// {
// return kozep;
// }
// else if(a[kozep]<x && a[kozep+1]>=x)
// {
// return kozep+1;
// }
// else if(x>a[kozep])
// {
// return binkeres(x,kozep+1,veg);
// }
// else
// {
// return binkeres(x,kezd,kozep-1);
// }
// }
// }
int binkeres(int x, int kezd, int veg)
{
int kozep;
while(kezd<=veg)
{
kozep=(kezd+veg)/2;
if(a[kozep]>=x && a[kozep-1]<x)
{
return kozep;
}
else if(a[kozep]<x && a[kozep+1]>=x)
{
return kozep+1;
}
else if(x>a[kozep])
{
//return binkeres(x,kozep+1,veg);
kezd=kozep+1;
}
else
{
// return binkeres(x,kezd,kozep-1);
veg=kozep-1;
}
}
}
// void binkeres(int x, int kezd, int veg)
// {
// //if(x==1)
// //{
// //cout<<kezd<<" "<<veg<<endl;
// //}
// if(veg-kezd==1)
// {
// if(x>a[kezd])
// {
// cout<<veg<<" ";
// return;
// }
// else
// {
// cout<<kezd<<" ";
// return;
// }
// }
// else
// {
// int kozep=(kezd+veg)/2;
// if(x==a[kozep])
// {
// //cout<<"alma";
// cout<<kozep<<" ";
// return;
// }
// else if(x<a[kozep])
// {
// binkeres(x,kezd,kozep-1);
// }
// else
// {
// binkeres(x,kozep+1,veg);
// }
// }
// }
int main()
{
int n,x,kdb;
cin>>n>>kdb;
//vector<int> a(n+1);
a[0]=0;
cin>>a[1];
for(int i=2;i<=n;i++)
{
cin>>x;
a[i]=a[i-1]+x;
//vlmi[prevveg]=i;
}
vector<int> kk(kdb);
int hossz=a[n];
for(int i=0;i<kdb;i++)
{
cin>>x;
kk[i]=x%hossz;
}
int k;
// auto seg=vlmi.end();
//prevveg++;
for(auto k: kk)
{
// cin>>k;
//k=k%(hossz);
if(k==0)
{
cout<<n<<" ";
continue;
}
if(k<a[1])
{
cout<<1<<" ";
}
else if(k>a[n-1])
{
//cout<<11111;
cout<<n<<" ";
}
else
{
cout<<binkeres(k,1,n)<<" ";
}
// //auto it=vlmi.begin();
// while (it!=seg && it->first<k)
// {
// it++;
// }
// //cout<<it->second<<" ";
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 2456 KiB | |||
2 | Elfogadva | 0/0 | 103ms | 3396 KiB | |||
3 | Elfogadva | 2/2 | 4ms | 3004 KiB | |||
4 | Elfogadva | 2/2 | 4ms | 3084 KiB | |||
5 | Elfogadva | 2/2 | 4ms | 3296 KiB | |||
6 | Elfogadva | 3/3 | 4ms | 3508 KiB | |||
7 | Elfogadva | 3/3 | 4ms | 3744 KiB | |||
8 | Elfogadva | 3/3 | 4ms | 3708 KiB | |||
9 | Elfogadva | 2/2 | 104ms | 4520 KiB | |||
10 | Elfogadva | 2/2 | 103ms | 4736 KiB | |||
11 | Elfogadva | 2/2 | 101ms | 4936 KiB | |||
12 | Elfogadva | 2/2 | 101ms | 5152 KiB | |||
13 | Elfogadva | 2/2 | 98ms | 5200 KiB | |||
14 | Elfogadva | 2/2 | 98ms | 5148 KiB | |||
15 | Elfogadva | 2/2 | 98ms | 5152 KiB | |||
16 | Elfogadva | 2/2 | 97ms | 5168 KiB | |||
17 | Elfogadva | 2/2 | 97ms | 5252 KiB | |||
18 | Elfogadva | 2/2 | 96ms | 5500 KiB | |||
19 | Elfogadva | 2/2 | 96ms | 5564 KiB | |||
20 | Elfogadva | 2/2 | 93ms | 5360 KiB | |||
21 | Elfogadva | 2/2 | 93ms | 5440 KiB | |||
22 | Elfogadva | 3/3 | 93ms | 5656 KiB | |||
23 | Elfogadva | 3/3 | 92ms | 5744 KiB | |||
24 | Elfogadva | 3/3 | 93ms | 5844 KiB |