Submission #631265

#	Time	Username	Problem	Language	Result	Execution time	Memory
631265		Hiennoob123	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	4.44 / 100	1098 ms	2476 KiB

brunhilda

#include<bits/stdc++.h>
#define ll int
#define ld double
#define cd complex<ld>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std ;
ll m , q ;
ll A[100005] = {} ;
void solve()
{
    cin >> m >> q ;
    for(int i = 1 ; i<= m ; i++) cin >> A[i] ;
    vector<ll> ans ;
    ll cur = 0 ;
    ans.push_back(0) ;
    while(cur<=10000000)
    {
        ll F = 0 ;
        for(int j = 1 ; j<= m ; j++)
        {
            F = max(F , cur-cur%A[j]+A[j]-1) ;
        }
        if(F<=cur) break ;
        ans.push_back(F) ;
        cur = F ;
    }
    //for(int i = 0 ; i< ans.size() ; i++) cout << ans[i] << "\n" ;
    for(int i = 1 ; i<= q ; i++)
    {
        ll k ; cin >> k ;
        ll save = k ;
        for(int j = 1 ; j<= m ; j++) save /= A[j] ;
        if(save>0)
        {
            cout << "oo\n" ;
            continue ;
        }
        ll lo = 0 , hi = ans.size() ;
        hi-- ;
        if(hi<0)
        {
            cout << "oo\n" ;
            continue ;
        }
        while(hi-lo>1)
        {
            ll mid = ((hi+lo)>>1) ;
            if(ans[mid]>k) hi = mid ;
            else lo = mid ;
        }
        if(ans[hi]<=k)
        {
            cout << hi ;
        }
        else cout << lo ;
        cout << "\n" ;
    }
}
int main()
{
    ios_base::sync_with_stdio(NULL) ; cin.tie(nullptr) ; cout.tie(nullptr) ;
    //freopen("LINES.inp" , "r" , stdin) ;
    //freopen("LINES.out" , "w" , stdout) ;
    //freopen("IN.txt" , "r" , stdin) ;
    int t = 1; //cin >> t ;
    for(int i = 1 ; i<= t ; i++)
    {
        solve() ;
    }
}

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