# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
248347 |
2020-07-12T09:23:12 Z |
VEGAnn |
Sirni (COCI17_sirni) |
C++14 |
|
5000 ms |
786436 KB |
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int N = 100100;
const int BIG = int(1e7) + 10;
const int cn = int(1e4);
const int oo = 2e9;
bool del[BIG];
vector<i2> edg;
vector<int> vc;
int mrk[BIG], n, nt[BIG];
ll ans = 0;
int get(int x) { return (x == nt[x] ? x : nt[x] = get(nt[x])); }
void calc(){
for (int i = BIG - 2; i > 0; i--)
if (mrk[i])
nt[i] = i;
else nt[i] = nt[i + 1];
for (int cr : vc){
int cm = mrk[cr];
int x = cr;
nt[get(x)] = get(x + 1);
for (int i = get(x); i < BIG - 1; ){
int nw = i % x;
edg.PB({i, x});
if (nw == 0)
i += x;
else i += x - nw;
i = get(i);
}
}
}
bool cmp(i2 _x, i2 _y){
return (_x[0] % _x[1]) < (_y[0] % _y[1]);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n;
for (int i = 1; i <= n; i++){
int x; cin >> x;
mrk[x] = i;
}
int siz = 0;
for (int i = 1; i < BIG; i++)
if (mrk[i]) {
siz++;
vc.PB(i);
}
nt[BIG - 1] = BIG - 1;
calc();
reverse(all(vc));
calc();
sort(all(edg), cmp);
for (int cr : vc)
nt[cr] = cr;
for (i2 nw : edg){
int x = get(nw[0]), y = get(nw[1]);
if (x == y) continue;
ans += nw[0] % nw[1];
nt[x] = y;
}
cout << ans << '\n';
return 0;
}
Compilation message
sirni.cpp: In function 'void calc()':
sirni.cpp:27:13: warning: unused variable 'cm' [-Wunused-variable]
int cm = mrk[cr];
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1582 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
39672 KB |
Output is correct |
2 |
Runtime error |
1475 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2321 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
457 ms |
52216 KB |
Output is correct |
2 |
Correct |
1481 ms |
76740 KB |
Output is correct |
3 |
Correct |
601 ms |
60388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
152 ms |
45676 KB |
Output is correct |
2 |
Correct |
870 ms |
75580 KB |
Output is correct |
3 |
Correct |
443 ms |
50792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
888 ms |
76912 KB |
Output is correct |
2 |
Correct |
1884 ms |
109604 KB |
Output is correct |
3 |
Correct |
557 ms |
60400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
213 ms |
44776 KB |
Output is correct |
2 |
Correct |
1843 ms |
109732 KB |
Output is correct |
3 |
Correct |
536 ms |
60384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5064 ms |
604548 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3913 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1774 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |