Submission #221092

#TimeUsernameProblemLanguageResultExecution timeMemory
221092aloo123Detecting Molecules (IOI16_molecules)C++14
100 / 100
84 ms8928 KiB
#include <bits/stdc++.h> #include "molecules.h" #define ll long long #define ld long double #define mp make_pair #define pb push_back #define vll vector<ll> #define endl "\n" #define pll pair<ll,ll> #define all(x) (x).begin() , (x).end() #define f first #define s second using namespace std; const ll N =(1e5+5); const ll MOD = 10243; const ll INF = 1e16; const ll LOG = 29; long long binpow(long long a, long long b) { a %= MOD; long long res = 1; while (b > 0) { if (b & 1) res = (res * a)%MOD ; a = (a * a)%MOD ; b >>= 1; } res%=MOD; return res; } vector<int> find_subset(int l, int u, vector<int> w){ ll n = w.size(); ll pre[n]; vector<pair<ll,ll>> gg; for(ll i = 0;i<n;i++){ gg.pb(mp(w[i],i)); } sort(all(gg)); pre[0]=gg[0].f; for(ll i =1;i<n;i++){ pre[i]=pre[i-1]+gg[i].f; } for(ll i =0;i<n;i++){ ll lo = i,hi=n-1; ll id = -1; while(lo<=hi){ ll j = (lo+hi)/2; ll sum = pre[j]; if(i != 0) sum-=pre[i-1]; if(sum<l){ lo=j+1; } else { if(sum>u){ hi=j-1; } else{ id=j; break; } } } if(id != -1){ vector<int> ans; for(int k = i;k<=id;k++){ ans.pb(gg[k].s); } sort(all(ans)); return ans; } } vector<int> ans; return ans; } // int main(){ // vector<int> v; // v.pb(6); // v.pb(8); // v.pb(8); // v.pb(7); // vector<int>x = find_subset(15,17,v); // for(auto xx:x)cout<<xx<<endl; // 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...