Submission #31943

#	Time	Username	Problem	Language	Result	Execution time	Memory
31943		Extazy	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	7.78 / 100	879 ms	65372 KiB

brunhilda

#include <bits/stdc++.h>
#define endl '\n'

#define left aklhgjqghkqkj
#define right ajklvhajkvhajk
#define prev aioghajga
#define next ioyhjhfajasj
#define y0 iuadoghasdgj
#define y1 taklahgjkla
#define remainder pogjuakllhga
#define pow pajklgaklha
#define pow10 iopuioadjlgkah
#define div aljghajkghak
#define distance gkuftgjasgfjh
#define uppercase ifyhasjkhakjfas
#define tm aogqjgklqjgqklgjqlkq

//#define floor hjakjhaja
//#define time ashjlahjka
//#define double_t double

using namespace std;

const int N = 1<<17;
const int TO = (1e6);
const int INF = (1e9) + 7;

multiset < int > s;
vector < int > div[TO + 7];
int dp[TO + 7];
int sv[TO + 7];
int n,q;
int mx;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j,x;
    multiset < int >::iterator it;

    scanf("%d %d", &n, &q);
    for(i=1;i<=n;i++) {
        scanf("%d", &x);
        mx=max(mx,x);

        if(!div[x].empty()) continue;

        for(j=x;j<=TO;j+=x) {
            div[j].push_back(x);
        }
    }

    for(i=1;i<=TO;i++) {
        for(j=0;j<(int)(div[i].size());j++) {
            if(div[i][j]!=i) {
                if((it=s.find(dp[sv[div[i][j]]]))!=s.end()) {
                    s.erase(it);
                    //s.erase(s.find(dp[sv[div[i][j]]]));
                }
            }
        }
        
        if(i<mx) dp[i]=1;
        else if(s.empty()) dp[i]=INF;
        else dp[i]=1+(*s.begin());
        dp[i]=min(dp[i],INF);

        for(j=0;j<(int)(div[i].size());j++) {
            sv[div[i][j]]=i;
            s.insert(dp[i]);
        }

        while(s.size()>7) {
            it=s.end();
            --it;
            s.erase(it);
        }
    }

    while(q--) {
        scanf("%d", &x);
        if(dp[x]==INF) printf("oo\n");
        else printf("%d\n", dp[x]);
    }

    return 0;
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:41:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
brunhilda.cpp:43:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^
brunhilda.cpp:81:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^

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