제출 #134033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134033		ly20	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	20 / 100	382 ms	262148 KiB

brunhilda

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+4,MAXQ=112345,INF=1123456789;
int resp[MAXN],p[MAXQ],r[MAXQ];
vector<int> seg,e,d;
vector<int> fat[MAXN];
int create()
{
    seg.push_back(INF);
    e.push_back(0);
    d.push_back(0);
    return seg.size()-1;
}
void update(int cur,int ini,int fim,int id,int val)
{
    if(ini>id || fim<id)return;
    if(ini==fim)
    {
        seg[cur]=val;
        return;
    }
    int m=(ini+fim)/2;
    if(id<=m)
    {
        if(e[cur]==0)
        {
            int aux=create();
            e[cur]=aux;
        }
        update(e[cur],ini,m,id,val);
    }
    else
    {
        if(d[cur]==0)
        {
            int aux=create();
            d[cur]=aux;
        }
        update(d[cur],m+1,fim,id,val);
    }
    seg[cur]=min(seg[e[cur]],seg[d[cur]]);
}
int main()
{
    create();create();
    int m,q;
    scanf("%d %d",&m,&q);
    int mp=0;
    for(int i=0;i<m;i++)
    {
        scanf("%d",&p[i]);
        mp=max(mp,p[i]);
    }
    int mq=0;
    for(int i=0;i<q;i++)
    {
        scanf("%d",&r[i]);mq=max(mq,r[i]);
    }
    for(int i=0;i<m;i++)for(int j=p[i];j<=mq;j+=p[i])fat[j].push_back(p[i]);
    for(int i=1;i<=mq;i++)
    {
        if(i>=mp)
        {
            resp[i]=INF;
            for(int j=0;j<fat[i].size();j++)
            {
                //printf("%d %d %d\n",i,fat[i][j],resp[i]);
                update(1,1,MAXN,fat[i][j],resp[i]);
            }
            resp[i]=seg[1]+1;
        }
        for(int j=0;j<fat[i].size();j++)
        {
            //printf("%d %d %d\n",i,fat[i][j],resp[i]);
            update(1,1,MAXN,fat[i][j],resp[i]);
        }
    }
    for(int i=0;i<q;i++)
    {
        if(resp[r[i]]<INF)printf("%d\n",resp[r[i]]+1);
        else printf("oo\n");
    }
    //for(int i=0;i<7;i++)printf("%d ",resp[i]);
    //printf("\n");
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:65:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<fat[i].size();j++)
                         ~^~~~~~~~~~~~~~
brunhilda.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<fat[i].size();j++)
                     ~^~~~~~~~~~~~~~
brunhilda.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&m,&q);
     ~~~~~^~~~~~~~~~~~~~~
brunhilda.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
         ~~~~~^~~~~~~~~~~~
brunhilda.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&r[i]);mq=max(mq,r[i]);
         ~~~~~^~~~~~~~~~~~

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