| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 221079 | 2020-04-09T13:48:27 Z | aloo123 | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KB |
#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
#define int ll
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){
int n = w.size();
int pre[n];
vector<pair<int,int>> gg;
for(int i = 0;i<n;i++){
gg.pb(mp(w[i],i));
}
sort(all(gg));
pre[0]=gg[0].f;
for(int i =1;i<n;i++){
pre[i]=pre[i-1]+gg[i].f;
}
for(int i =0;i<n;i++){
int lo = i,hi=n-1;
int id = -1;
while(lo<=hi){
int j = (lo+hi)/2;
int 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;
// }