Submission #31858

#	Time	Username	Problem	Language	Result	Execution time	Memory
31858		ngkan146	Brunhilda’s Birthday (BOI13_brunhilda)	C++98	100 / 100	473 ms	80532 KiB

brunhilda

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
const int MAX = (int) 1e7;
int madiv[MAX+5];
int m,q;
int p[100005];
int dp[MAX+5];
void prep(){
   for(int i=1;i<=m;i++)
      for(int j=0;j<=MAX;j+=p[i])
         madiv[j] = p[i];
}
int main(){
   //freopen("BRUNHILDA.inp","r",stdin);
   //freopen("BRUNHILDA.out","w",stdout);
   scanf("%d %d",&m,&q);
   for(int i=1;i<=m;i++)
      scanf("%d",&p[i]);
   prep();
   for(int i=1;i<=MAX;i++) dp[i] = 10*MAX;
   int ctrl = 0;

   for(int i=1;i<=MAX;i++){
      while(ctrl < i && ctrl + madiv[ctrl]-1 < i) ++ctrl;
      if (ctrl == i) break;

      dp[i] = dp[ctrl] + 1;
   }

   for(int i=1;i<=q;i++){
      int n;
      scanf("%d",&n);
      if (dp[n] >= MAX) printf("oo\n");
      else printf("%d\n",dp[n]);
   }
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&m,&q);
                        ^
brunhilda.cpp:21:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&p[i]);
                        ^
brunhilda.cpp:35:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&n);
                     ^

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