Submission #968688

#	Time	Username	Problem	Language	Result	Execution time	Memory
968688		RandomUser	Spiderman (COCI20_spiderman)	C++17	70 / 70	106 ms	17492 KiB

spiderman

#include <bits/stdc++.h>
//#define int long long
  
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
  
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;
  
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
  
    int n, h;
    cin >> n >> h;
  
    vector<int> v(n);
    set<int> diff;
    for(int &x : v) cin >> x, diff.insert(x);
      
     if(h == 0) {
        vector<int> ans(1e6+1), cnt(1e6+1);
        for(int &x : v) cnt[x]++;
   
        for(int i=1; i<=1e6; i++) {
            if(!cnt[i]) continue;
            for(int j=2*i; j<=1e6; j+=i) ans[j] += cnt[i];
        }
   
        for(int i=0; i<n; i++) cout << ans[v[i]] + cnt[v[i]] - 1 << " ";
        return 0;
    }
   
    if(diff.size() <= 2000) {
        vector<pii> vec;
        vector<int> v2(n);
        map<int, int> mp;
        vector<int> ans(n);
   
        for(int &x : v) mp[x]++;
   
        for(auto &[a, b] : mp) vec.push_back({ a, b });
   
        for(int i=0; i<vec.size(); i++) {
            for(int j=0; j<vec.size(); j++) {
                if(i == j) continue;
                if(vec[i].first % vec[j].first == h) v2[i] += vec[j].second;
            }
        }
   
        for(int i=0; i<n; i++) {
            auto p = lower_bound(vec.begin(), vec.end(), make_pair(v[i], 0)) - vec.begin();
            ans[i] = v2[p];
        }
   
        for(int &x : ans) cout << x << " ";
        return 0;
    }
   
    if(n <= 2000) {
        for(int i=0; i<n; i++) {
            int ans = 0;
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                if(v[i] % v[j] == h) ans++;
            }
            cout << ans << " ";
        }
        return 0;
    }
  
    //glhf!!!!
    vector<int> ans(n);
    int B = 0;
    for(int &x : v) B += (x > h);
  
    for(int i=0; i<n; i++) {
        if(v[i] != h) continue;
        ans[i] += B;
    }
  
    vector<int> cnt(1e6+1);
    for(int &x : v) cnt[x]++;
    vector<int> arr(1e6+1);
  
    for(int i=h+1; i<=1e6; i++) {
        for(int j=i; j<=1e6; j+=i) arr[j+h] += cnt[i];
    }
  
    for(int i=0; i<n; i++) cout << ans[i] + arr[v[i]] << " ";
    return 0;
}

Compilation message (stderr)

spiderman.cpp: In function 'int32_t main()':
spiderman.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i=0; i<vec.size(); i++) {
      |                      ~^~~~~~~~~~~
spiderman.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for(int j=0; j<vec.size(); j++) {
      |                          ~^~~~~~~~~~~

• Subtask 1: 70 / 70