Submission #212063

# Submission time Handle Problem Language Result Execution time Memory
212063 2020-03-22T08:02:24 Z NONAME Spiderman (COCI20_spiderman) C++17
56 / 70
469 ms 8824 KB
#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] << " ";
}

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2688 KB Output is correct
2 Correct 9 ms 1792 KB Output is correct
3 Correct 42 ms 4216 KB Output is correct
4 Correct 120 ms 7216 KB Output is correct
5 Incorrect 398 ms 5624 KB Output isn't correct
6 Incorrect 426 ms 8824 KB Output isn't correct
7 Correct 450 ms 5624 KB Output is correct
8 Correct 462 ms 5628 KB Output is correct
9 Correct 466 ms 8696 KB Output is correct
10 Correct 469 ms 8568 KB Output is correct