Submission #1175201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175201		nuutsnoynton	Sirni (COCI17_sirni)	C++20	84 / 140	5108 ms	793488 KiB

sirni

#include<bits/stdc++.h>

using namespace std;
using ll = int;
const ll N = 1e7 + 2;
ll a[100005];
ll ataman[100005];
ll Get(ll x) {
	if (x == ataman[x]) return x;
	return ataman[x] = Get(ataman[x]);
}

void Unite(ll x, ll y) {
	x = Get(x);
	y = Get(y);
	if ( x == y) return ;
	if ( x > y) swap(x, y);
	ataman[y] = x;
}

int main() {
	ll n, m, r, x, y, i, j, ans, t;

	cin >> n;
	
	set < ll > S;
	
	for (i = 1; i <= n; i ++) {
		cin >> x;
		S.insert(x);
	} 
	n = S.size(); 
	
	r = 1;
	for (ll X : S) {
		a[r] = X;
		r ++;
	}
	vector < pair < ll, pair < ll, ll > > > v;

	for (i = 1; i <= n; i ++) {
		for ( j = 2 * a[i]; j <= a[n]; j += a[i]) {
			r = lower_bound(a + 1, a + n + 1, j) - a;
			if ( r> n) break;
			v.push_back(make_pair(a[r] - j, make_pair(i, r)));
		}
	}
	
	for (i = 1; i < n; i ++) {
		v.push_back(make_pair(a[i + 1] %a[i],make_pair(i , i + 1) ));
	}
	
	for (i = 1; i <= n; i ++) ataman[i] = i;
	ans = 0;
	sort(v.begin(), v.end());
	
	for (i = 0; i < v.size(); i ++) {
		x = v[i].second.first;
		y = v[i].second.second;
		x = Get(x);
		y = Get(y);
		if ( x != y) {
			Unite(x, y);
			ans += v[i].first;
		}
	}
	
	cout << ans << endl;
}

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