Submission #212070

#	Time	Username	Problem	Language	Result	Execution time	Memory
212070		NONAME	Spiderman (COCI20_spiderman)	C++17	56 / 70	480 ms	8720 KiB

spiderman

#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define F first
#define S second
#define sz(x) int(x.size())

using namespace std;


int b[1000005];

int main()
{
    //freopen("army.in","r",stdin); freopen("army.out","w",stdout);
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, k;

    cin >> n >> k;

    pair <int, int>  a[n];

    for (int i = 0; i < n; i++) {a[i].S = i; cin >> a[i].F; b[a[i].F]++; }

    sort(a, a + n);

    int ans[n];

    for (int i = 0; i < n; i++)
    {
        if (k > a[i].F) {ans[a[i].S] = 0; continue;}

        if (i != 0 && a[i - 1].F == a[i].F) {ans[a[i].S] = ans[a[i - 1].S]; continue;}

        if (k == a[i].F) {ans[a[i].S] = n - i - b[a[i].F]; continue;}

        ans[a[i].S] = 0;

        int sg = sqrt(a[i].F - k), ost = a[i].F - k;

        for (int j = 2; j <= sg; j++)
        {
            if (ost % j != 0) continue;

            if (a[i].F % j == k) ans[a[i].S] += b[j];

            int div = ost / j;

            if (div > sg && a[i].F % div == k) ans[a[i].S] += b[div];
        }

        if (a[i].F % ost == k) ans[a[i].S] += b[ost];
    }

    for (int i = 0; i < n; i++) cout << ans[i] << " ";
}

• Subtask 1: 56 / 70