Submission #197991

#	Time	Username	Problem	Language	Result	Execution time	Memory
197991		ami	Spiderman (COCI20_spiderman)	C++17	70 / 70	155 ms	11476 KiB

spiderman

#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 / 70