# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
248373 |
2020-07-12T10:04:01 Z |
VEGAnn |
Sirni (COCI17_sirni) |
C++14 |
|
5000 ms |
786436 KB |
#include <bits/stdc++.h>
#define ft first
#define sd second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define i2 array<int,2>
#define pis pair<int,short>
using namespace std;
typedef long long ll;
const int N = 100100;
const int BIG = int(1e7) + 10;
const int con = (1 << 10) - 1;
const int oo = 2e9;
int mrk[BIG];
vector<pis> edg;
vector<int> vc;
int n, a[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;
for (int i = nt[x + 1]; i < BIG - 1; ){
int nw = i % x;
edg.PB({(mrk[i] << 10) + (mrk[x] & con), (mrk[x] >> 10)});
if (nw == 0)
i += x;
else i += x - nw;
i = nt[i];
}
}
}
bool cmp(pis _x, pis _y){
int x1 = (_x.ft >> 10), x2 = (_x.sd << 10) + (_x.ft & con);
int y1 = (_y.ft >> 10), y2 = (_y.sd << 10) + (_y.ft & con);
return (a[x1] % a[x2]) < (a[y1] % a[y2]);
}
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;
a[i] = x;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++){
int x = a[i];
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();
sort(all(edg), cmp);
for (int cr : vc)
nt[cr] = cr;
for (pis _x : edg){
int x = (_x.ft >> 10), y = (_x.sd << 10) + (_x.ft & con);
x = a[x];
y = a[y];
int xx = get(x), yy = get(y);
if (xx == yy) continue;
ans += x % y;
nt[xx] = yy;
}
cout << ans << '\n';
return 0;
}
Compilation message
sirni.cpp: In function 'void calc()':
sirni.cpp:30:13: warning: unused variable 'cm' [-Wunused-variable]
int cm = mrk[cr];
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1517 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 |
82 ms |
39672 KB |
Output is correct |
2 |
Runtime error |
1428 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 |
2262 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 |
476 ms |
52584 KB |
Output is correct |
2 |
Correct |
1620 ms |
77732 KB |
Output is correct |
3 |
Correct |
640 ms |
61408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
45804 KB |
Output is correct |
2 |
Correct |
959 ms |
76636 KB |
Output is correct |
3 |
Correct |
466 ms |
51176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
966 ms |
77168 KB |
Output is correct |
2 |
Correct |
2064 ms |
110624 KB |
Output is correct |
3 |
Correct |
576 ms |
61412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
44904 KB |
Output is correct |
2 |
Correct |
1927 ms |
110620 KB |
Output is correct |
3 |
Correct |
592 ms |
61280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5092 ms |
786436 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3791 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 |
1917 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |