Submission #1175135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175135		Nomio	Sirni (COCI17_sirni)	C++20	0 / 140	727 ms	95288 KiB

sirni

#include<bits/stdc++.h>
#define s second
#define f first
using namespace std;
using ll = long long;

const int maxn = 1e5 + 1;
const int MAXN = 1e7 + 1;

vector<int> pos(MAXN, -1);
int a[maxn], sz[maxn], p[maxn];

int find(int x) {
	if(a[x] == x) return x;
	return a[x] = find(a[x]);
}

int unite(int u, int v) {
	u = find(u);
	v = find(v);
	if(u == v) return -1;
	if(sz[u] > sz[v]) swap(u, v);
	sz[v] += sz[u];
	a[u] = v;
	return v;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	multiset<int> s;
	for(int i = 0; i < n; i++) {
		a[i] = i;
		sz[i] = 1;
	}
	for(int i = 0; i < n; i++) {
		cin >> p[i];
		if(pos[p[i]] == -1) pos[p[i]] = i;
		s.insert(p[i]);
	}
	sort(p, p + n);
	vector<pair<int, pair<int, int>>> edge;
	for(int i = 1; i < n; i++) {
		if(p[i] == p[i - 1]) {
			unite(i, i - 1);
			s.erase(i);
		}
	}
	vector<int> v;
	for(int x : s) {
		v.push_back(x);
	}
	int N = v.size();
	for(int i = 0; i < N; i++) {
		s.erase(v[i]);
		for(int j = 2; j * v[i] <= v[N - 1]; j++) {
			int x = *s.lower_bound(j * v[i]);
			edge.push_back({x % v[i], {pos[v[i]], pos[x]}});
		}
	}
	sort(edge.begin(), edge.end());
	ll ans = 0;
	for(pair<int, pair<int, int>> p : edge) {
		int u = p.s.f;
		int v = p.s.s;
		int d = p.f;
		int V = unite(u, v);
		ans += d;
		if(V != -1) {
			if(sz[V] == n) {
				cout << ans << '\n';
				return 0;
			}
		}
	}
	return 0;
}

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