Submission #1131603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131603		sunflower	Spiderman (COCI20_spiderman)	C++17	70 / 70	48 ms	14152 KiB

spiderman

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int numHouse, remMod;

#define MAX_N 300'005
int high[MAX_N + 2];

#define LIM 1'000'007
int cnt[2 * LIM + 2], dp[2 * LIM + 2];

namespace subtask1 {
    bool check() {
        return (numHouse <= 2000);
    }

    void solve() {
        FOR(i, 1, numHouse) {
            int ans = 0;
            FOR(j, 1, numHouse) {
                if (i == j) continue;
                if (high[i] % high[j] == remMod) ++ans;
            }

            cout << ans << " ";
        }
    }
}

namespace subtask3 {
    bool check() {
        return (remMod == 0);
    }

    void solve() {
        memset(cnt, 0, sizeof(cnt));
        FOR(i, 1, numHouse) cnt[high[i]]++;

        FOR(i, 1, trunc(sqrt(LIM))) {
            dp[i * i] += cnt[i];
            FOR(j, i + 1, LIM / i) {
                dp[i * j] += cnt[i];
                dp[i * j] += cnt[j];
            }
        }

        FOR(i, 1, numHouse) cout << dp[high[i]] - 1 << " "; // tru chinh no;
    }
}

namespace subtask4 {
    void solve() {
        memset(cnt, 0, sizeof(cnt));
        FOR(i, 1, numHouse) cnt[high[i]]++;

        FOR(i, 1, trunc(sqrt(LIM))) {
            if (i > remMod) dp[i * i] += cnt[i];
            FOR(j, i + 1, LIM / i) {
                if (i > remMod) dp[i * j] += cnt[i];
                if (j > remMod) dp[i * j] += cnt[j];
            }
        }

        FORD(i, LIM - 1, 1) cnt[i] += cnt[i + 1];

        // a / b = q du r ==> a = b * q + r (b > r);

        FOR(i, 1, numHouse) {
            if (remMod > high[i]) cout << "0 ";
            else if (remMod == high[i]) {
                cout << cnt[high[i] + 1] << " ";
            } else { // high[j] * MUL + remMod = high[i];
                cout << dp[high[i] - remMod] - (remMod == 0) << " ";
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    // freopen("spiderman.inp","r",stdin);
    // freopen("spiderman.out","w",stdout);
    cin >> numHouse >> remMod;
    FOR(i, 1, numHouse) cin >> high[i];

//    if (subtask1 :: check()) return subtask1 :: solve(), 0;
    subtask4 :: solve();

    return 0;
}

• Subtask 1: 70 / 70