Submission #436836

#	Time	Username	Problem	Language	Result	Execution time	Memory
436836		penguinhacker	Sirni (COCI17_sirni)	C++14	140 / 140	2932 ms	612280 KiB

sirni

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5, mxP=1e7; // change to 1e7
int n, nxt[mxP+1], ind[mxP+1], n2, p[mxN];
vector<ar<int, 2>> e[mxP];

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin >> n;
	//n=100000;
	for (int i=0; i<n; ++i) {
		int x;
		cin >> x;
		//x=rng()%9999000+1000;
		nxt[x]=x;
	}
	for (int i=1; i<=mxP; ++i)
		if (nxt[i])
			ind[i]=n2++;
	for (int i=mxP-1; i; --i)
		if (!nxt[i])
			nxt[i]=nxt[i+1];
	if (nxt[1]==1) {
		cout << 0;
		return 0;
	}
	for (int i=2; i<mxP; ++i) {
		if (i^nxt[i])
			continue;
		if (nxt[i+1]<2*i&&nxt[i+1])
			e[nxt[i+1]-i].push_back({ind[i], ind[nxt[i+1]]});
		for (int j=2*i; j<=mxP&&nxt[j]; j+=i)
			if (nxt[j]<j+i)
				e[nxt[j]-j].push_back({ind[i], ind[nxt[j]]});
	}
	//sort(e.begin(), e.end());
	iota(p, p+n2, 0);
	int ans=0, cmp=n2;
	for (int i=0; i<mxP; ++i)
		for (ar<int, 2> a : e[i]) {
			int u=find(a[0]), v=find(a[1]);
			if (u^v) {
				p[v]=u;
				--cmp;
				ans+=i;
			}
		}
	assert(cmp==1);
	cout << ans;
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14