Submission #844374

#	Time	Username	Problem	Language	Result	Execution time	Memory
844374		vjudge1	Spiderman (COCI20_spiderman)	C++17	0 / 70	404 ms	23380 KiB

spiderman

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1e6 + 5, MOD = 1e9 + 7;

ll cnt[N], ans[N];
map<ll, ll> mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, k, a = 0;
    cin >> n >> k;
    
    vector<int> vec(n);

    for(int i = 0; i < n; i++)
    {
        cin >> vec[i];
        cnt[vec[i]]++;

        if(vec[i] > k)
            a++;
    }    

    ans[0] = a;

    for(ll i = 0; i < n; i++)
    {
        ll x = vec[i] - k;
        if(x > 0 and !mp[x])
        {
            mp[x] = true;
            for(ll j = 1; j * j <= x; j++)
            {
                if(x % j == 0)
                {
                    ans[x] = (j <= k ? 0 : cnt[j]);
                    if(x / j != j)
                        ans[x] += (x / j <= k ? 0 : cnt[x / j]);
                }
            }
        }
    }

    for(int i = 0; i < n; i++)
    {
        if(vec[i] < k)
            cout << 0 << " ";
        else
            cout << ans[vec[i] - k] << " ";
    }

    cout << '\n';
}

• Subtask 1: 0 / 70