# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
248359 |
2020-07-12T09:45:12 Z |
VEGAnn |
Sirni (COCI17_sirni) |
C++14 |
|
0 ms |
0 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];
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({(mrk[i] << 10) + (mrk[x] & con), (mrk[x] >> 10)});
if (nw == 0)
i += x;
else i += x - nw;
i = get(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 'int get(int)':
sirni.cpp:21:31: error: 'nt' was not declared in this scope
int get(int x) { return (x == nt[x] ? x : nt[x] = get(nt[x])); }
^~
sirni.cpp:21:31: note: suggested alternative: 'n'
int get(int x) { return (x == nt[x] ? x : nt[x] = get(nt[x])); }
^~
n
sirni.cpp: In function 'void calc()':
sirni.cpp:26:13: error: 'nt' was not declared in this scope
nt[i] = i;
^~
sirni.cpp:26:13: note: suggested alternative: 'n'
nt[i] = i;
^~
n
sirni.cpp:27:14: error: 'nt' was not declared in this scope
else nt[i] = nt[i + 1];
^~
sirni.cpp:27:14: note: suggested alternative: 'n'
else nt[i] = nt[i + 1];
^~
n
sirni.cpp:34:9: error: 'nt' was not declared in this scope
nt[get(x)] = get(x + 1);
^~
sirni.cpp:34:9: note: suggested alternative: 'n'
nt[get(x)] = get(x + 1);
^~
n
sirni.cpp:30:13: warning: unused variable 'cm' [-Wunused-variable]
int cm = mrk[cr];
^~
sirni.cpp: In function 'int main()':
sirni.cpp:86:5: error: 'nt' was not declared in this scope
nt[BIG - 1] = BIG - 1;
^~
sirni.cpp:86:5: note: suggested alternative: 'n'
nt[BIG - 1] = BIG - 1;
^~
n