Submission #1069826

#TimeUsernameProblemLanguageResultExecution timeMemory
1069826kiethm07Detecting Molecules (IOI16_molecules)C++11
100 / 100
39 ms8784 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define iii pair<int,pii> #define fi first #define se second #define vi vector<int> #define vii vector<pii> #define pb(i) push_back(i) #define all(x) x.begin(),x.end() #define TEXT "a" using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int inf = 1e9 + 7; const ld eps = 1e-8; const double pi = acos(-1); vector<int> find_subset(int l,int r,vector<int> w){ int n = w.size(); vector<pii> a(n); for (int i = 0; i < n; i++){ a[i] = pii(w[i],i); } sort(all(a)); vector<ll> pre(n), suf(n); pre[0] = 0; for (int i = 1; i < n; i++){ pre[i] = pre[i - 1] + a[i].fi - a[0].fi; } suf[n - 1] = a[n - 1].fi - a[0].fi; for (int i = n - 2; i >= 0; i--){ suf[i] = suf[i + 1] + a[i].fi - a[0].fi; } vector<int> res; for (ll x = 1; x <= n; x++){ ll c = l - x * a[0].fi; ll d = r - x * a[0].fi; if (pre[x - 1] > d || suf[n - x] < c) continue; for (int r = x - 1; r < n; r++){ int l = r - x; int pR = pre[r]; int pL = l < 0 ? 0 : pre[l]; if (pR - pL >= c){ for (int j = l + 1; j <= r; j++){ res.push_back(a[j].se); } break; } } break; } return res; }
#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...