Submission #26574

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

brunhilda

#include<bits/stdc++.h>
using namespace std;
#define inf (int)1e6
int n,m;
int p[100005];
int last[100005];
int pos[10000005];
int rec[10000005];
int mem[10000005];
main() {
    int i,j,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[0]++;
        last[i] = 0;
    }
    for(i=1,j=0;i<=10000000;i++) {
        x = i;
        while(rec[x]) {
            pos[last[rec[x]]]--;
            last[rec[x]] = i;
            pos[last[rec[x]]]++;
            x = x/p[rec[x]];
        }
        while(j<i && pos[j]==0) j++;
        if(i==j) mem[i] = inf;
        else mem[i] = mem[j] + 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:36:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^

• Subtask 1: 15.555555555555555 / 20
• Subtask 2: 14.444444444444445 / 20
• Subtask 3: 35.714285714285715 / 60