Submission #31872

#	Time	Username	Problem	Language	Result	Execution time	Memory
31872		Kanvie	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	5.56 / 100	649 ms	41928 KiB

brunhilda

#include<bits/stdc++.h>
using namespace std;
const int M=10000000;
int x,m,q,d[M+1],mx,p,pp,cnt;
vector<int>v;
int main()
{
    cin>>m>>q;
    while(m--)
    {
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    m=v.size();
    for(int i=0;i<m;++i)
    {
        x=v[i];
        for(int j=0;j<=M;j+=x)d[j]=x;
    }
    p=v[v.size()-1]-1;
    pp=v[v.size()-1]-1;
    cnt=1;
    for(int i=1;i<=M;++i)
    {
        if(i<=p)
        {
            if(d[i]!=0)pp=max(pp,i+d[i]-1);
            d[i]=cnt;
            if(i==p)
            {
                p=pp;
                cnt++;
            }
        }
        else {mx=i-1;break;}
    }
    while(q--)
    {
        cin>>x;
        if(mx<x)cout<<"oo\n";
        else cout<<d[x]<<"\n";
    }
}

• Subtask 1: 5.555555555555555 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60