제출 #1167961

#제출 시각아이디문제언어결과실행 시간메모리
1167961Saul0906Sirni (COCI17_sirni)C++20
56 / 140
697 ms851968 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("avx2") #pragma GCC target("popcnt") using namespace std; using ll = long long; using ull = unsigned long long; using lld = long double; using ii = pair<int,int>; using pll = pair<ll, ll>; using vi = vector<int>; using vll = vector<ll>; using vii = vector<ii>; using vpll = vector<pll>; using vlld = vector<lld>; #define all(x) x.begin(),x.end() #define lsb(x) x&(-x) #define gcd(a,b) __gcd(a,b) #define sz(x) (int)x.size() #define mp make_pair #define pb push_back #define fi first #define se second #define fls cout.flush() #define fore(i, l, r) for (auto i = l; i < r; i++) #define fo(i, n) fore (i, 0, n) #define forex(i, r, l) for (auto i = r-1; i >= l; i--) #define ffo(i, n) forex (i, n, 0) bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; } bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; } void valid(ll in) { cout<<((in)?"YES\n":"NO\n"); } ll lcm(ll a, ll b) { return (a/gcd(a,b))*b; } ll gauss(ll n) { if(n<0) return 0; return (n*(n+1))/2; } mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll INF = 1e18; struct DSU { vll pa; ll n, gr; DSU (ll n): n(n), gr(n), pa(n+2, 0) { fo (i, n+2) pa[i] = i; } ll find (ll i) { return pa[i] == i ? i : pa[i] = find(pa[i]); } void unite (ll i, ll j) { i = find(i); j = find(j); if (i == j) return; if (i > j) swap(i, j); gr--; pa[j] = i; } }; void test_case () { ll n; cin >> n; vll a(n); fo (i, n) cin >> a[i]; sort(all(a)); a.erase(unique(all(a)), a.end()); n = sz(a); ll mx = *max_element(all(a)); vll idx(mx+1, -1), vis(n+1, -1); vector<vll> cmps; fo (i, n) idx[a[i]] = i; if (a[0] == 1 || n == 1) { cout << "0\n"; return; } {DSU ok(n); for (ll i = 1; i <= mx; i++) { if (idx[i] == -1) continue; for (ll j = 2*i; j <= mx; j += i) { if (idx[j] == -1) continue; ok.unite(idx[i], idx[j]); } } ll id = 0; fo (i, n) { ll j = ok.find(i); if (vis[j] == -1 ) vis[j] = id++, cmps.pb({}); cmps[vis[j]].pb(i); } } ll ans = 0; while (sz(cmps) > 1) { vector<vector<pll>> prv(mx+2, vpll(2, mp(-1, -1))), nxt(mx+2, vpll(2, mp(-1, -1))); vll st(mx+2, -1); vector<array<ll, 2>> mul(mx+2, {-1, -1}); fo (c, sz(cmps)) { for (ll i: cmps[c]) { st[a[i]] = c; for (ll j = a[i]; j <= mx; j += a[i]) { if (mul[j][0] == -1) mul[j][0] = c; else mul[j][1] = c; } } } fore (i, 1, mx+1) { if (min(mul[i][0], mul[i][1]) > -1 && mul[i][0] != mul[i][1]) { prv[i] = {{i, mul[i][0]}, {i, mul[i][1]}}; continue; } prv[i] = prv[i-1]; if (mul[i][0] == -1) continue; prv[i][0] = {i, mul[i][0]}; if (mul[i][0] != prv[i-1][0].se) { prv[i][1] = prv[i-1][0]; } } forex (i, mx+1, 1) { nxt[i] = nxt[i+1]; if (st[i] == -1) continue; nxt[i][0] = {i, st[i]}; if (st[i] != nxt[i+1][0].se) nxt[i][1] = nxt[i+1][0]; } DSU ok(sz(cmps)); fo (c, sz(cmps)) { array<ll, 2> bst = {INF, -1}; for (ll i: cmps[c]) { for (ll j = a[i]; j <= mx; j += a[i]) { pll p = {-1, -1}; if (nxt[j][0].se != c) p = nxt[j][0]; else p = nxt[j][1]; if (p == mp(-1ll, -1ll)) continue; if (p.fi-j < bst[0]) bst = {p.fi-j, p.se}; } pll p = {-1, -1}; if (prv[a[i]][0].se != c) p = prv[a[i]][0]; else p = prv[a[i]][1]; if (p == mp(-1ll, -1ll)) continue; if (a[i]-p.fi < bst[0]) bst = {a[i]-p.fi, p.se}; } if (bst[1] >= 0 && ok.find(c) != ok.find(bst[1])) { ans += bst[0]; ok.unite(c, bst[1]); } } if (ok.gr == 1) break; vis = vll(sz(cmps), -1); vector<vll> ncmps(ok.gr); ll id = 0; fo (c, sz(cmps)) { ll nc = ok.find(c); if (vis[nc] == -1 ) vis[nc] = id++; for (ll i: cmps[c]) { ncmps[vis[nc]].pb(i); } } cmps = ncmps; } cout << ans << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int tt = 1; while (tt--) test_case(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...