Submission #1059739

#TimeUsernameProblemLanguageResultExecution timeMemory
1059739underwaterkillerwhaleSirni (COCI17_sirni)C++17
140 / 140
879 ms574908 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (int)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 1e7 + 2; const int Mod = 1e9 + 7; const ll INF = 2e9 + 7; const ll BASE = 137; const int szBL = 320; const int N2 = 1e5 + 7; int n, m; int nxt[N], a[N2]; vector<pii> edges[N]; struct disjoin_set { int lab[N2], sz[N2]; void init (int n) { rep (i, 1, n) lab[i] = i, sz[i] = i; } int Find (int u) { if (u == lab[u]) return u; return lab[u] = Find(lab[u]); } bool Join (int u, int v) { u = Find(u); v = Find(v); if (u == v) return 0; if (sz[u] < sz[v]) swap(u, v); sz[u] += sz[v]; lab[v] = u; return 1; } }DSU; void solution () { cin >> n; rep (i, 1, n) cin >> a[i]; sort (a + 1, a + 1 + n); n = unique(a + 1, a + 1 + n) - a - 1; m = *max_element(a + 1, a + 1 + n); DSU.init(n); rep (i, 1, n) nxt[a[i]] = i; reb (i, m, 1) { if (!nxt[i]) nxt[i] = nxt[i + 1]; } rep (i, 1, n) { if (nxt[a[i] + 1] && a[nxt[a[i] + 1]] < a[i] * 2) { edges[a[nxt[a[i] + 1]] - a[i]].pb({i, nxt[a[i] + 1]}); } for (int j = a[i] * 2; j <= m; j += a[i]) { if (nxt[j] && a[nxt[j]] < j + a[i]) { edges[a[nxt[j]] - j].pb({i, nxt[j]}); } } } ll res = 0; rep (i, 0, m) { iter(&ed, edges[i]) if (DSU.Join(ed.fs, ed.se)) { res += i; } } cout << res <<"\n"; } // #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +2 2 + 8 * 2 - 9 7 7 0 2 5 0 1 1 2 1 2 2 2 1 4 4 1 4 6 2 6 3 3 */
#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...