Submission #140454

#TimeUsernameProblemLanguageResultExecution timeMemory
140454bazsi700Detecting Molecules (IOI16_molecules)C++14
100 / 100
63 ms7160 KiB
#include <bits/stdc++.h> #include "molecules.h" using namespace std; #define MOD 1000000007 #define ll long long int #define vi vector<int> #define vii vector< vector<int> > #define PI 3.1415926535897932384626433832795 #define INF 9223372036854775807LL #define hashA 1257958787 #define hashB 1539500609 #define endl "\n" vector<int> find_subset(int l, int u, vector<int> w) { int n = w.size(); vector<pair<ll,int> > vec (n); ll sum = 0; vector<int> ans; for(int i = 0; i < n; i++) { vec[i] = {w[i],i}; if(l <= w[i] && w[i] <= u) { ans.push_back(i); return ans; } sum+= w[i]; } sort(vec.begin(),vec.end()); if(vec[0].first > u || sum < l) { return ans; } ll minsum = 0; ll maxsum = 0; for(int cn = 1; cn <= n; cn++) { minsum+= vec[cn-1].first; maxsum+= vec[n-cn].first; if(minsum > u) { break; } if(maxsum < l) { continue; } if(minsum >= l) { for(int i = 0; i < cn; i++) { ans.push_back(vec[i].second); } break; } if(maxsum <= u) { for(int i = 0; i < cn; i++) { ans.push_back(vec[n-1-i].second); } break; } queue<int> que; for(int i = 0; i < cn; i++) { que.push(vec[i].second); } for(int j = 0; j < cn && minsum < l; j++) { que.pop(); que.push(vec[n-1-j].second); minsum-= vec[j].first; minsum+= vec[n-1-j].first; } while(!que.empty()) { ans.push_back(que.front()); que.pop(); } } return ans; }
#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...