oj.uz

Submission #489875

# Submission time Handle Problem Language Result Execution time Memory
489875 2021-11-25T02:25:08 Z 8e7 Sirni (COCI17_sirni) C++17
14 / 140
 2126 ms 32092 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 100005
#define maxc 10000005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
bool rig[maxc], lef[maxc];
int dis[maxn];
bool found[maxn];
priority_queue<pii, vector<pii>, greater<pii> > pq;
vector<int> a;
int n;
void upd(int x) {
	
	for (int i = x;i < maxc;i += x) {
		if (!rig[i]) {
			rig[i] = 1;
			int ind = lower_bound(a.begin(), a.end(), i) - a.begin();
			if (ind < n && !found[ind] && a[ind] - i < dis[ind]) {
				dis[ind] = a[ind] - i;	
				pq.push({dis[ind], ind});
			}
			ind++;
			if (ind < n && !found[ind] && a[ind] - i < dis[ind]) {
				dis[ind] = a[ind] - i;	
				pq.push({dis[ind], ind});
			}
		}
	}
	int tmp = x;
	for (int i = 1;i * i <= x;i++) {
		tmp = x / i;
		if (!lef[tmp]) {
			lef[tmp] = 1;
			int ind = upper_bound(a.begin(), a.end(), tmp) - a.begin()-1;
			if (ind >= 0 && !found[ind] && x % a[ind] < dis[ind]) {
				dis[ind] = x % a[ind];
				pq.push({dis[ind], ind});
			}	
			ind--;
			if (ind >= 0 && !found[ind] && x % a[ind] < dis[ind]) {
				dis[ind] = x % a[ind];
				pq.push({dis[ind], ind});
			}
		}	
	}
	for (;tmp >= 1;tmp--) {
		if (!lef[tmp]) {
			lef[tmp] = 1;
			int ind = upper_bound(a.begin(), a.end(), tmp) - a.begin()-1;
			if (ind >= 0 && !found[ind] && x % a[ind] < dis[ind]) {
				dis[ind] = x % a[ind];
				pq.push({dis[ind], ind});
			}
			ind--;
			if (ind >= 0 && !found[ind] && x % a[ind] < dis[ind]) {
				dis[ind] = x % a[ind];
				pq.push({dis[ind], ind});
			}
		}	
	}
}
int main() {
	io
	cin >> n;
	a.resize(n, 0);
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	a.resize(int(unique(a.begin(), a.end()) - a.begin()));
	n = a.size();
	dis[0] = 0;
	found[0] = 1;
	for (int i = 1;i < n;i++) dis[i] = 1<<30;
	upd(a[0]);
	int ans = 0;
	while (pq.size()) {
		pii cur = pq.top();pq.pop();
		if (cur.ff != dis[cur.ss] || found[cur.ss]) continue;
		ans += cur.ff;
		found[cur.ss] = 1;
		upd(a[cur.ss]);	
	}
	cout << ans << endl;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14788 KB Output is correct
2 Incorrect 107 ms 14976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 10172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15300 KB Output is correct
2 Correct 24 ms 9680 KB Output is correct
3 Correct 29 ms 16136 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 830 ms 14240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 12028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 967 ms 14032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 11444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1915 ms 23876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2126 ms 32092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 413 ms 20680 KB Output isn't correct
2 Halted 0 ms 0 KB -