Гарри Поттер и Узник Азкабана HackerEarth Конкурентное программирование Вопрос

Question

Во-первых, я не знаю, где задать вопрос на основе конкурентного программирования, но это проблема кодирования, поэтому я задаю этот вопрос здесь.

Ссылка на проблему: https://www.hackerearth.com/problem/algorithm/harry-gets-into-infy/

ОК. Я узнал, что мне нужно обработать все значения, прежде чем на самом деле работать над запросами. Я запрограммировал это в соответствии с моими умственными способностями.

Мой код:

#include <iostream>
#include <math.h>

using namespace std;

const int size = 1000000;

int factors[size+1];
int query[size+1];

void printQuery(){
    for(int i=1;i<=20;i++){
        cout << query[i] << " ";
    }
    cout << endl;
}

void printFactors(){
    for(int i=1;i<=20;i++){
        cout << factors[i] << " ";
    }
    cout << endl;
}

void mark(int fac){
  if(factors[fac])
    return;
  factors[fac]=1;
}

void makeQueryArray(){
  for(int i=1;i<=size;i++){
    if(factors[i]){
     for(int j=i;j<=size;j+=i){
       if(query[j]<i)
        query[j]=i;
     }
    }
  }
}

int main(){
  int n, q;
  cin >> n >> q;
  int* arr = new int[n];
  for(int i=0;i<n;i++){
    cin >> arr[i];
    for(int j=1;j<=sqrt(arr[i]);j++){
      if(arr[i]%j==0){
        int fac1 = j;
        int fac2 = arr[i]/j;
        mark(fac1);
        mark(fac2);
      }
    }
  }
  int* queries = new int[q];
  for(int i=0;i<q;i++)
    cin >> queries[i];
  makeQueryArray();
  for(int i=0;i<q;i++){
    int qu = queries[i];
    if(!query[qu])
        cout << "1" << endl;
    else 
        cout << query[qu] << endl;
  }
  return 0;
}

Я просто получаю значения из массива и разлагаю их и размечаю значения в другой массив и вызывается в запросе. Я думал, что это достаточно хорошо, чтобы пометить все значения раньше, потому что использование euler для всего лишь дало TLE. Я не знаю, где мне не хватает. Я пытался заглянуть в редакцию этой проблемы и не смог ее понять. Я не очень уверен, где мне не хватает этой вещи. Есть ли алгоритм, о котором я не знаю, или логика c, которую я не могу придумать.

Я вставляю редакционную логику c. Пожалуйста, объясните мне редакционную статью, если это возможно.

Редакция:

#include<bits/stdc++.h>

#define pb push_back
#define len(n) n.length()
#define mp make_pair
#define forp(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,n)    for(int i=0;i<n;i++)
#define ren(i,n)    for(int i=n-1;i>=0;i--)
#define forn(i,a,b) for(int i=a;i>=b;i--)
#define fre    freopen("in","r",stdin),freopen(y + ".out","w",stdout)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define alll(n,i,j) n.begin()+i,n.begin()+j
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL)
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define mem(n,m) memset(n,m,sizeof(n))
#define bitc(n) __builtin_popcount(n)
#define mod 1000000007
#define mod2 1000000009
#define ma(m,n) m = max(m,n)
#define mi(m,n) m = min(m,n)
#define EPSILON 1e-6
#define PI 3.14159265358979323846

#define TRACE

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif
using namespace std;
typedef unsigned long long int ULL;
typedef long long int LL;
typedef vector<vector<LL> > mat;
#define N 1000005
#define LD long double

static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;

template <typename T> T mulmod(T a,T b, T m){LL q=(LL)(((LD)a*(LD)b)/(LD)m);LL r=a*b-q*m;if(r>m)r%=m;if(r<0)r+=m;return r;}
template <typename T> T MOD(T a, T b) {return (a < b ? a : a % b);}
template <typename T>T expo(T e, T n){T x=1,p=e;while(n){if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
template <typename T>T power(T e, T n, T m){T x=1,p=e;while(n){if(n&1)x=mulmod(x,p,m);p=mulmod(p,p,m);n>>=1;}return x;}
template <typename T> T gcd(T a, T b){if(a%b) return gcd(b,a%b);return b;}
template <typename T> T lcm(T a, T b){return (a*(b/gcd(a,b)));}
template <typename T> T add (T a, T b, T Mod) {a += b; return (a >= Mod ? a - Mod : a);}
template <typename T> T sub (T a, T b, T Mod) {a -= b; return (a < 0 ? a + Mod : a);}

int a[N], g[N], Query[N];

int main () {
 boost;
 int n, q;
 cin >> n >> q;
 forp (i,1,n) {
  int x;
  cin >> x;
  a[x] = true; 
 }
 for (int i = 1; i <= 1e6; i++) {
    for (int j = i; j <= 1e6; j += i) {
      g[i] |= a[j];  
    }
 }
 vector <int> qu;
 while (q--) {
  int x;
  cin >> x;
  Query[x] = 1;
  qu.pb (x);
 }
 for (int i = 1; i <= 1e6; i++) {
    if (!g[i]) continue;
    for (int j = i; j <= 1e6; j += i) { 
       if (Query[j]) {
         Query[j] = i;
       }
    }
 }
 for (int x : qu) {
   cout << Query[x] << "\n";
 }
 return 0;
}

Пожалуйста, помогите мне, и если этот вопрос выходит за рамки этого сообщества, то, пожалуйста, скажите мне, где задавать конкурентные проблемы программирования.

Заранее спасибо.