Submission #155736

#	Time	Username	Problem	Language	Result	Execution time	Memory
155736		IOrtroiii	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	426 ms	87416 KiB

brunhilda

#include <bits/stdc++.h>

using namespace std;

const int MX = 10 * 1000 * 1000 + 7;

bool has[MX];
int nxt[MX];
int ans[MX];

int main() {
   int n, q;
   scanf("%d %d", &n, &q);
   for (; n > 0; n--) {
      int x;
      scanf("%d", &x);
      has[x] = true;
   }
   for (int i = 2; i < MX; ++i) {
      if (!has[i]) continue;
      for (int j = 0; j < MX; j += i) {
         nxt[j] = max(nxt[j], j + i - 1);
      }
   }
   int ptr = 0;
   for (int i = 1; i < MX; ++i) {
      while (ptr < i && nxt[ptr] < i) {
         ++ptr;
      }
      if (ptr == i) {
         break;
      } else ans[i] = ans[ptr] + 1;
   }
   for (; q > 0; q--) {
      int x;
      scanf("%d", &x);
      if (!ans[x]) {
         puts("oo");
      } else {
         printf("%d\n", ans[x]);
      }
   }
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:13:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &n, &q);
    ~~~~~^~~~~~~~~~~~~~~~~
brunhilda.cpp:16:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &x);
       ~~~~~^~~~~~~~~~
brunhilda.cpp:36:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &x);
       ~~~~~^~~~~~~~~~

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