#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl
vector<int> p(int n) {
int x = n;
vector<int> p;
for (int i = 2;i<sqrt(n)+1 || i==3 || i==2;i++) {
if (x==0) return p;
if (x%i == 0) {
p.push_back(i);
while (x%i==0) x/=i;
}
}
return p;
}
struct node{
int val;
vector<int> adj;
};
int32_t main() {
int n,k;cin>>n>>k;
map<int,int> seen;
vp h(n);for (int i = 0;i<n;i++) {
int x;cin>>x;
h[i] = {x,i};
seen[x] = 1;
}
vector<node> nodes(1e6+1);
vector<int> res(n);
for (int i=0;i<nodes.size();i++) {
nodes[i].val = i+1;
}
sort(h.begin(),h.end());
for (int i = 0;i<n;i++) {
auto v = p(h[i].first-k);
res[h[i].second] = (k==h[i].first?n-i-1:0);
if (!v.size()) continue;
for (int j = 0;j<v.size();j++) {
if (v[j]<=k || seen[v[j]]==0) continue;
nodes[h[i].first].adj.push_back(v[j]);
}
queue<int> q;
q.push(h[i].first);
map<int,int> mp;
int amt = 0;
while (q.size()) {
auto f = q.front();
if (mp[f]) {q.pop();continue;}
mp[f]=1;
amt++;
for (int j = 0;j<nodes[f].adj.size();j++) {
//if (nodes[nodes[f].adj[j]].val <= k) continue;
q.push(nodes[f].adj[j]);
}
q.pop();
}
amt--;
res[h[i].second] += amt;
//cout<<h[i].first<<" "<<amt<<endl;
}
for (int i = 0;i<n;i++) {
cout<<res[i]<<" ";
}cout<<endl;
return 0;
}
Compilation message
spiderman.cpp: In function 'int32_t main()':
spiderman.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i=0;i<nodes.size();i++) {
| ~^~~~~~~~~~~~~
spiderman.cpp:51:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int j = 0;j<v.size();j++) {
| ~^~~~~~~~~
spiderman.cpp:65:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int j = 0;j<nodes[f].adj.size();j++) {
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
32032 KB |
Output isn't correct |
| 2 |
Incorrect |
15 ms |
31832 KB |
Output isn't correct |
| 3 |
Incorrect |
651 ms |
34068 KB |
Output isn't correct |
| 4 |
Incorrect |
1657 ms |
37160 KB |
Output isn't correct |
| 5 |
Incorrect |
361 ms |
40564 KB |
Output isn't correct |
| 6 |
Incorrect |
1020 ms |
45320 KB |
Output isn't correct |
| 7 |
Incorrect |
380 ms |
38544 KB |
Output isn't correct |
| 8 |
Incorrect |
384 ms |
39504 KB |
Output isn't correct |
| 9 |
Incorrect |
1142 ms |
44056 KB |
Output isn't correct |
| 10 |
Incorrect |
1116 ms |
42612 KB |
Output isn't correct |
