Submission #1080754

#TimeUsernameProblemLanguageResultExecution timeMemory
1080754ALeonidouDetecting Molecules (IOI16_molecules)C++17
69 / 100
68 ms15300 KiB
#include "molecules.h" #include <bits/stdc++.h> using namespace std; #define ll int #define F first #define S second #define pb push_back #define sz(x) (ll)x.size() typedef vector <ll> vi; typedef pair<ll,ll> ii; typedef vector <ii> vii; #define dbg(x) cout<<#x<<": "<<x<<endl; #define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl; #define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl; void printVct(vi &v){ for (ll i =0; i<sz(v); i++){ cout<<v[i]<<" "; } cout<<endl; } #define ins insert ll s; set <ll> st; vii c; void add(ll idx){ st.ins(idx); s += c[idx].F; } void rem(ll idx){ st.erase(idx); s -= c[idx].F; } vi find_subset(int l, int r, vi cc) { c.resize(sz(cc)); vi mp(sz(c)); for (ll i =0; i<sz(c); i++){ c[i] = ii(cc[i], i); } sort(c.begin(), c.end()); for (ll i =0; i<sz(c); i++){ mp[i] = c[i].S; } // printVct(mp); // cout<<"c: "; // for (ll i=0; i<sz(c); i++){ // cout<<c[i].F<<" "; // } // cout<<endl; ll n = sz(c), p = 0; s = 0; while (p < n && s < l){ add(p); p++; } p--; if (s < l){ //impossible to reach l return vi(); } if (s > r){ rem(p); p--; } // dbg(p); ll m = min(p, n-p-2); p = 0; // dbg2(s,m); while (p <= m && s < l){ // dbg(1); rem(p); add(n-p-1); p++; } if (s < l) return vi(); // dbg(s); vi ans; for (set <ll> :: iterator it = st.begin(); it != st.end(); it++){ ans.pb(mp[*it]); } sort(ans.begin(), ans.end()); return ans; } /* 5 16 22 10 13 14 16 12 4 15 17 6 8 8 7 10 50 51 8 9 9 8 9 8 9 8 8 8 */
#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...