oj.uz

Submission #197991

# Submission time Handle Problem Language Result Execution time Memory
197991 2020-01-24T12:42:25 Z ami Spiderman (COCI20_spiderman) C++17
70 / 70
 155 ms 11476 KB 
#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
using namespace std;
using ll = long long;

int const MAXH=1000001;
int freq[MAXH];
int res[MAXH];

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	int N,K;
	cin>>N>>K;
	vector<int> h(N);
	fore(h,&i) {
		cin>>i;
		freq[i]++;
	}

	auto hh=h;

	sort(h.begin(),h.end());
	h.erase(unique(h.begin(),h.end()),h.end());

	fore(h,x) if (x>K) {
		// h_i < h_j -> K == h_i
		if (freq[K]) res[K]+=freq[x];

		// h_i >= h_j
		for (int c=(K==0?2:1); c*x+K<=MAXH; c++) if (freq[c*x+K]) res[c*x+K]+=freq[x];
	}

	if (K==0) {
		// h_i == h_j -> K == 0
		fore(h,x) res[x]+=freq[x]-1;
	}

	rep(i,0,sz(hh)) cout<<res[hh[i]]<<" \n"[i+1==sz(hh)];
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4856 KB Output is correct
2 Correct 10 ms 3064 KB Output is correct
3 Correct 41 ms 6264 KB Output is correct
4 Correct 93 ms 8056 KB Output is correct
5 Correct 89 ms 9208 KB Output is correct
6 Correct 152 ms 11476 KB Output is correct
7 Correct 73 ms 9208 KB Output is correct
8 Correct 106 ms 9188 KB Output is correct
9 Correct 151 ms 11384 KB Output is correct
10 Correct 155 ms 11372 KB Output is correct