# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
644037 | 2022-09-23T15:33:09 Z | mohammedMonem | Spiderman (COCI20_spiderman) | C++17 | 6 ms | 8212 KB |
#include<bits/stdc++.h> using namespace std; #define endl '\n' [[maybe_unused]] typedef long long ll; [[maybe_unused]] const int N = (int)1e6 + 54; [[maybe_unused]] const int mod = (int)1e9 + 7; [[maybe_unused]] char space = ' '; void Run(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif } int n,k; vector<int> isPrime(N,1); vector<int> primes; ll fastPow(ll x,ll y) { if (y == 0) { return 1; } return fastPow(x,y / 2) * fastPow(x,y / 2) * (y % 2 ? x : 1); } void sieve() { isPrime[0] = isPrime[1] = 0; for (ll i = 2; i * i <= N; i++) { if (!isPrime[i]) { continue; } for (ll j = i * i; j * j <= N; j += i) { isPrime[j] = 0; } primes.push_back(int(i)); } } vector<int> freq(N); vector<int> ans; map<int,int> primeDiv; vector<int> divs; void div(auto i = primeDiv.begin(),int res = 1,int h = 0) { if (i == primeDiv.end()) { divs.push_back(res); return; } auto temp = i; temp++; for (int j = 0; j <= i -> second; j++) { div(temp,res * fastPow(i -> first,j)); } } void add(int h) { primeDiv.clear(); divs.clear(); int temp = h; for (const auto &item: primes) { while (temp % item == 0) { primeDiv[item]++; temp /= item; } } if (temp != 1) { primeDiv[temp]++; } div(primeDiv.begin(),1,h); } int main() { Run(); //pre sieve(); //in int t = 1; // cin >> t; while (t--) { cin >> n >> k; vector<int> h(n); for (int i = 0; i < n; i++) { cin >> h[i]; } //ops ans.resize(n); int cnt = 0; for (const auto &item: h) { freq[item] += item > k; } for (int i = 0; i < n; i++) { if (h[i] > k) { cnt++; add(h[i] - k); for (const auto &item: divs) { ans[i] += freq[item]; } } } //out for (int i = 0; i < n; i++) { cout << ans[i] + cnt * (h[i] == k) << space; } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 8148 KB | Output isn't correct |
2 | Incorrect | 5 ms | 8148 KB | Output isn't correct |
3 | Incorrect | 5 ms | 8184 KB | Output isn't correct |
4 | Incorrect | 5 ms | 8148 KB | Output isn't correct |
5 | Incorrect | 5 ms | 8148 KB | Output isn't correct |
6 | Incorrect | 5 ms | 8148 KB | Output isn't correct |
7 | Incorrect | 6 ms | 8148 KB | Output isn't correct |
8 | Incorrect | 5 ms | 8148 KB | Output isn't correct |
9 | Incorrect | 6 ms | 8212 KB | Output isn't correct |
10 | Incorrect | 5 ms | 8148 KB | Output isn't correct |