Submission #209336

#TimeUsernameProblemLanguageResultExecution timeMemory
209336papaSpiderman (COCI20_spiderman)C++14
70 / 70
1320 ms13404 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxv = 1e6; const int maxn = 3*1e5; int cnt[maxv + 5]; int p[maxv + 5]; int a[maxn+5]; int k; int n; int res[maxn+5]; int res2[maxn+5]; void input() { cin >> n >> k; for(int i=1;i<=n;i++) cin >> a[i]; } void output() { for(int i=1;i<=n;i++) cout << res[i] << " "; } void brute() { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) continue; if(a[i]%a[j]==k) res2[i]++; } } } int randd(int a,int b) { return a+rand()%(b-a+1); } void testprimer() { n = 4000; k = randd(0,1e6); for(int i=1;i<=n;i++) { a[i] = randd(1,1e6); } } bool uporedi() { for(int i=1;i<=n;i++) if(res[i]!=res2[i]) return false; return true; } void razlika() { cout << n << " " << k << "\n"; for(int i=1;i<=n;i++) { cout << a[i] << " "; } cout << "\n"; cout << "Resi" << "\n"; for(int i=1;i<=n;i++) { cout << res[i] << " "; } cout << "\n"; cout << "Brute" << "\n"; for(int i=1;i<=n;i++) { cout << res2[i] << " "; } cout << "\n"; exit(0); } int resi(int x) { int rs = 0; for(int i=1;i*i<=x;i++) { if(x%i==0) { int d1 = i; int d2 = x/i; if(d1==d2) { rs+=(d1 > k) ? cnt[d1] : 0; } else { rs+=(d1 > k) ? cnt[d1] : 0; rs+=(d2 > k) ? cnt[d2] : 0; } } } return rs; } void resii() { for(int i=1;i<=n;i++) cnt[a[i]]++; p[maxv] = cnt[maxv]; for(int i=maxv-1;i>=1;i--) p[i] = p[i+1] + cnt[i]; for(int i=1;i<=n;i++) { if(a[i] < k) { res[i] = 0; continue; } if(a[i]==k) { res[i] = p[a[i]+1]; continue; } cnt[a[i]]--; res[i] = resi(a[i]-k); cnt[a[i]]++; } } void restart() { for(int i=1;i<=n;i++) res[i]=res2[i] = 0; for(int i=1;i<=maxv;i++) cnt[i]=0; } void testiraj() { int brprim = 20; for(int i=1;i<=brprim;i++) { restart(); testprimer(); brute(); resii(); if(!uporedi()) { razlika(); } else { cout << "OK" << "\n"; } } } void r() { input(); resii(); output(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0); bool tt = 0; if(tt) testiraj(); else r(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...