Submission #31849

#	Time	Username	Problem	Language	Result	Execution time	Memory
31849		ngkan146	Brunhilda’s Birthday (BOI13_brunhilda)	C++98	100 / 100	606 ms	155564 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(){
   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;
   deque <ii> dq;
   dq.push_back(ii(0,madiv[0]-1));

   for(int i=1;i<=MAX;i++){
      while(dq.size() && dq.front().fi + dq.front().se < i) dq.pop_front();
      if (!dq.size()) break;
      assert(dq.size());
      dp[i] = dp[dq.front().fi] + 1;
      dq.push_back(ii(i,madiv[i]-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:17: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:19:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&p[i]);
                        ^
brunhilda.cpp:34: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