Submission #711685

#TimeUsernameProblemLanguageResultExecution timeMemory
711685JANCARAPANDetecting Molecules (IOI16_molecules)C++17
69 / 100
40 ms5432 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define all(a) (a).begin(), (a).end() #define sz(a) (long long) a.size() #define endl '\n' #define dbg(a) cerr << #a << " = " << a << endl; #define print(a) for (auto x : a) cerr << x << " "; cerr << endl; const long long INF = 1e18, MOD = 1e9+7; vector<int> find_subset(int l, int r, vector<int> tmp) { int n = sz(tmp); vector<pair<int,int>> a(n); for (int i = 0; i < n; i++) { a[i] = {tmp[i], i}; } sort(all(a)); vector<int> pref(n), suff(n); for (int i = 0; i < n; i++) { pref[i] = a[i].fi + (i ? pref[i - 1] : 0); suff[n - i - 1] = a[n - i - 1].fi + (i ? suff[n - i] : 0); } vector<int> ans; for (int size = 0; size < n; size++) { if (pref[size] > r || suff[n - size - 1] < l) continue; int cur = pref[size]; int j = 0; while (cur < l && j <= size) { cur += a[n - j - 1].fi - a[j].fi; j += 1; } if (cur >= l) { assert(cur <= r); for (int it = j; it <= size; it++) { ans.pb(a[it].se); } for (int it = n - 1; it >= n - j; it--) { ans.pb(a[it].se); } break; } } set<int> st(all(ans)); assert(sz(st) == sz(ans)); return ans; } //signed main() { //ios_base::sync_with_stdio(0); //cin.tie(0); //vector<int> a = find_subset(15, 17, {6, 6, 8, 7}); //vector<int> a = find_subset(11, 11, {1, 2, 3, 4}); //vector<int> a = find_subset(10, 20, {15, 17, 16, 18}); //for (auto x : a) cerr << x << " "; //} //signed main() { //ios_base::sync_with_stdio(0); //cin.tie(0); //int tt = 1; //cin >> tt; //while (tt--) { //solve(); //} //return 0; //}
#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...