oj.uz

Submission #436827

# Submission time Handle Problem Language Result Execution time Memory
436827 2021-06-25T03:01:07 Z penguinhacker Sirni (COCI17_sirni) C++14
98 / 140
 5000 ms 473512 KB 
#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, 3>> e;

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.push_back({nxt[i+1]-i, ind[i], ind[nxt[i+1]]});
		for (int j=2*i; j<=mxP&&nxt[j]; j+=i)
			if (nxt[j]<j+i)
				e.push_back({nxt[j]-j, ind[i], ind[nxt[j]]});
	}
	sort(e.begin(), e.end());
	iota(p, p+n2, 0);
	int ans=0, cmp=n2;
	for (ar<int, 3> a : e) {
		int u=find(a[1]), v=find(a[2]);
		if (u^v) {
			p[v]=u;
			--cmp;
			ans+=a[0];
		}
	}
	assert(cmp==1);
	cout << ans;
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 43204 KB Output is correct
2 Correct 151 ms 44552 KB Output is correct
3 Correct 74 ms 43572 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 39620 KB Output is correct
2 Correct 406 ms 40812 KB Output is correct
3 Correct 73 ms 43588 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 43444 KB Output is correct
2 Correct 73 ms 41852 KB Output is correct
3 Correct 74 ms 43460 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 56496 KB Output is correct
2 Correct 1020 ms 93420 KB Output is correct
3 Correct 423 ms 68760 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 46600 KB Output is correct
2 Correct 550 ms 92388 KB Output is correct
3 Correct 304 ms 54648 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 93420 KB Output is correct
2 Correct 1281 ms 142720 KB Output is correct
3 Correct 392 ms 68756 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 46772 KB Output is correct
2 Correct 1199 ms 142576 KB Output is correct
3 Correct 375 ms 68812 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 104140 KB Output is correct
2 Execution timed out 5075 ms 473512 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 104212 KB Output is correct
2 Execution timed out 5092 ms 472364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 76944 KB Output is correct
2 Execution timed out 5104 ms 465304 KB Time limit exceeded
3 Halted 0 ms 0 KB -