제출 #440557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440557		mashrur_hossain	Spiderman (COCI20_spiderman)	C++14	0 / 70	806 ms	100288 KiB

spiderman

#include <bits/stdc++.h>

#define fast_cin         ios_base::sync_with_stdio(0); cin.tie(NULL); cerr.tie(NULL);
#define endl "\n"
#define dbg(x) cerr << #x << ": " << x << endl;
#define DBG    cerr << __LINE__ << ": I GOT STUCK\n";

using namespace std;    
typedef long long ll;
typedef long double db;


const int mxn = 1e6 + 10;
vector<int>divisors[mxn];
void sieve(){
    for(int i = 1;i*i < mxn;i++){
        for(int j = i;j < mxn;j+=i){
            divisors[j].push_back(i);
        }
    }
}

void solve(){
    int n, k;cin >> n >> k;
    vector<int>freq(mxn), ans(mxn);
    int h[n];
    for(int i = 0;i<n;i++){
        cin >> h[i];
        freq[h[i]]++;
    }
    int tot = 0;
    for(int i = 1;i<mxn;i++){
        if(freq[i] == 0)continue;
        tot += freq[i];
        if(i == k){
            ans[i] += n - tot;
        }
        else if(i > k){
            int x = i - k;
            for(auto d: divisors[x]){
                if(i % d == k)ans[i] += freq[d];
            }
            if(x == i)--ans[i];
        }
    }
    for(int i =0 ;i<n;i++){
        cout << ans[h[i]]  << " \n"[i == n-1];
    }

}

int main() {
    fast_cin;
    int test;test = 1;
    // int test;cin >>test;
    while(test--){
        sieve();
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 70