Submission #26570

#	Time	Username	Problem	Language	Result	Execution time	Memory
26570		top34051	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	16.83 / 100	1000 ms	85680 KiB

brunhilda

#include<bits/stdc++.h>
using namespace std;
#define inf (int)1e6
int n,m;
int p[100005];
int last[100005];
int rec[10000005];
int mem[10000005];
multiset<int> pos;
main() {
    int i,x;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) {
        scanf("%d",&p[i]);
        x = p[i];
        while(x<=10000000) {
            rec[x] = i;
            x += p[i];
        }
        pos.insert(0);
        last[i] = 0;
    }
    for(i=1;i<=10000000;i++) {
        x = i;
        while(rec[x]) {
            pos.erase(pos.find(last[rec[x]]));
            last[rec[x]] = i;
            pos.insert(last[rec[x]]);
            x = x/p[rec[x]];
        }
        mem[i] = inf;
        mem[i] = min(mem[i],mem[*pos.begin()] + 1);
    }
    while(m--) {
        scanf("%d",&x);
        if(mem[x]==inf) printf("oo\n");
        else printf("%d\n",mem[x]);
    }
}

Compilation message (stderr)

brunhilda.cpp:10:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
brunhilda.cpp: In function 'int main()':
brunhilda.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
brunhilda.cpp:14:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
                          ^
brunhilda.cpp:35:23: 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: 3.3333333333333335 / 20
• Subtask 3: 5.714285714285714 / 60