oj.uz

Submission #968688

# Submission time Handle Problem Language Result Execution time Memory
968688 2024-04-23T20:16:07 Z RandomUser Spiderman (COCI20_spiderman) C++17
70 / 70
 106 ms 17492 KB 
#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

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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB Output is correct
2 Correct 6 ms 604 KB Output is correct
3 Correct 47 ms 2704 KB Output is correct
4 Correct 102 ms 6996 KB Output is correct
5 Correct 51 ms 14164 KB Output is correct
6 Correct 106 ms 16464 KB Output is correct
7 Correct 50 ms 14416 KB Output is correct
8 Correct 62 ms 14768 KB Output is correct
9 Correct 104 ms 17492 KB Output is correct
10 Correct 105 ms 17488 KB Output is correct