# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
23100 |
2017-05-03T05:27:12 Z |
model_code |
Sirni (COCI17_sirni) |
C++11 |
|
5000 ms |
720640 KB |
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
typedef long long ll;
typedef pair<int, int> P;
#define X first
#define Y second
const int MAXN = 1<<19, MAXM = 1e7 + 5;
vector <P> V[MAXM];
int najbliz[MAXM];
int p[MAXN];
int n;
int root[MAXN], rnk[MAXN];
int bio[MAXM], ozn[MAXM];
int find(int x)
{
if (root[x] == -1) return x;
return root[x] = find(root[x]);
}
void merge(int a, int b)
{
a = find(a);
b = find(b);
assert(a != b);
if (rnk[a] > rnk[b]) root[b] = a;
else if (rnk[b] > rnk[a]) root[a] = b;
else {
rnk[a]++;
root[b] = a;
}
}
int main()
{
scanf("%d", &n);
memset(ozn, -1, sizeof ozn);
REP(i, n) {
scanf("%d", &p[i]);
najbliz[p[i]] = p[i];
if (ozn[p[i]] == -1)
ozn[p[i]] = i;
}
for (int i=MAXM-2; i>=0; i--)
if (!najbliz[i])
najbliz[i] = najbliz[i+1];
REP(i, n) {
if (bio[p[i]]++) continue;
if (najbliz[p[i]+1]) {
if (2*p[i] >= MAXM || najbliz[2*p[i]] != najbliz[p[i]+1])
V[najbliz[p[i]+1] - p[i]].push_back(P(i, ozn[najbliz[p[i]+1]]));
}
for (int j=2*p[i]; j<MAXM && najbliz[j]; j+=p[i])
if (j + p[i] >= MAXM || najbliz[j+p[i]] != najbliz[j])
V[najbliz[j]-j].push_back(P(i, ozn[najbliz[j]]));
}
memset(root, -1, sizeof root);
ll rje = 0;
REP(i, MAXM)
REP(j, (int) V[i].size())
if (find(V[i][j].X) != find(V[i][j].Y)) {
merge(V[i][j].X, V[i][j].Y);
rje += i;
}
REP(i, n) if (ozn[p[i]] == i) { assert(find(i) == find(0)); }
printf("%lld\n", rje);
return 0;
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:50:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
sirni.cpp:53:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p[i]);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
359856 KB |
Output is correct |
2 |
Correct |
179 ms |
362364 KB |
Output is correct |
3 |
Correct |
99 ms |
359988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
359856 KB |
Output is correct |
2 |
Correct |
366 ms |
360524 KB |
Output is correct |
3 |
Correct |
113 ms |
359988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
359856 KB |
Output is correct |
2 |
Correct |
119 ms |
359724 KB |
Output is correct |
3 |
Correct |
119 ms |
359988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
219 ms |
372416 KB |
Output is correct |
2 |
Correct |
323 ms |
407284 KB |
Output is correct |
3 |
Correct |
256 ms |
377696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
361552 KB |
Output is correct |
2 |
Correct |
293 ms |
384192 KB |
Output is correct |
3 |
Correct |
179 ms |
371624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
306 ms |
387820 KB |
Output is correct |
2 |
Correct |
349 ms |
424668 KB |
Output is correct |
3 |
Correct |
206 ms |
376612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
119 ms |
363760 KB |
Output is correct |
2 |
Correct |
399 ms |
416716 KB |
Output is correct |
3 |
Correct |
229 ms |
374680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
373 ms |
373856 KB |
Output is correct |
2 |
Correct |
3033 ms |
624232 KB |
Output is correct |
3 |
Correct |
389 ms |
376896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
389 ms |
374316 KB |
Output is correct |
2 |
Execution timed out |
5000 ms |
720640 KB |
Execution timed out |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
361968 KB |
Output is correct |
2 |
Execution timed out |
5000 ms |
712896 KB |
Execution timed out |
3 |
Halted |
0 ms |
0 KB |
- |