oj.uz

Submission #212070

# Submission time Handle Problem Language Result Execution time Memory
212070 2020-03-22T08:25:10 Z NONAME Spiderman (COCI20_spiderman) C++17
56 / 70
 480 ms 8720 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] << " ";
}

Subtask #1
56.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 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 104 ms 7032 KB Output is correct
5 Incorrect 405 ms 5624 KB Output isn't correct
6 Incorrect 428 ms 8720 KB Output isn't correct
7 Correct 452 ms 5624 KB Output is correct
8 Correct 453 ms 5624 KB Output is correct
9 Correct 470 ms 8568 KB Output is correct
10 Correct 480 ms 8696 KB Output is correct