Submission #548367

#	Time	Username	Problem	Language	Result	Execution time	Memory
548367		Amylopectin	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	35 ms	2752 KiB

brunhilda

#include <iostream>
#include <stdio.h>

using namespace std;
const long long mxn = 2e5 + 10,mxm = 1e7 + 10;
long long pri[mxn] = {},nli[mxm] = {};
long long fima(long long l,long long r)
{
    if(l > r)
        return l;
    return r;
}
int main()
{
    long long i,j,n,m,cou = 0,cn,fn,cma,mu = 1,cl,cr,mid,p;
    scanf("%lld %lld",&n,&m);
    for(i=0; i<n; i++)
    {
        scanf("%lld",&pri[i]);
        mu *= pri[i];
        if(mu > 10000000)
            mu = 10000001;
    }
    nli[0] = 0;
    for(i=1; 1; i++)
    {
        cma = nli[i-1];
        for(j=n-1; j>=0; j--)
        {
            if(pri[j] <= cma - nli[i-1])
                break;
            cn = pri[j] - (nli[i-1] % pri[j]) - 1 + nli[i-1];
            if(cn > cma)
            {
                cma = cn;
                fn = pri[j];
            }

//            cma = fima(cma,);
        }
        nli[i] = cma;
//        if(i<100)
//            printf("%lld %lld %lld\n",i,fn,cma);
        if(cma >= mu-1)
            break;
    }
    p = i;
//    for(j=0; j<=i; j++)
//    {
//        printf("%d\n",nli[j]);
//    }
    for(i=0; i<m; i++)
    {
        scanf("%lld",&cn);
        if(cn >= mu)
        {
            printf("oo\n");
            continue;
        }
        cl = 0;
        cr = p;
        while(cl < cr)
        {
            mid = (cl+cr)/2;
            if(nli[mid] >= cn)
            {
                cr = mid;
            }
            else
                cl = mid+1;
        }
        printf("%lld\n",cl);
    }
    return 0;
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:15:23: warning: unused variable 'cou' [-Wunused-variable]
   15 |     long long i,j,n,m,cou = 0,cn,fn,cma,mu = 1,cl,cr,mid,p;
      |                       ^~~
brunhilda.cpp:15:34: warning: variable 'fn' set but not used [-Wunused-but-set-variable]
   15 |     long long i,j,n,m,cou = 0,cn,fn,cma,mu = 1,cl,cr,mid,p;
      |                                  ^~
brunhilda.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%lld",&pri[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%lld",&cn);
      |         ~~~~~^~~~~~~~~~~~

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