Submission #31093

#TimeUsernameProblemLanguageResultExecution timeMemory
31093TAMREFDetecting Molecules (IOI16_molecules)C++11
100 / 100
83 ms4536 KiB
#include "molecules.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; vector<int> I, ans; vector<int> find_subset(int l, int u, std::vector<int> w) { int n=w.size(); I=vector<int>(n); iota(I.begin(),I.end(),0); sort(I.begin(),I.end(),[&w](int u, int v){return w[u]<w[v];}); long long fsum=0, rsum=0; for(int i=0;i<n;i++){ fsum+=w[I[i]], rsum+=w[I[n-1-i]]; if(fsum>u) return vector<int>(0); if(l<=fsum && fsum<=u){ ans.assign(I.begin(),I.begin()+i+1); return ans; } if(l<=rsum && rsum<=u){ ans.assign(I.begin()+n-1-i,I.end()); return ans; } if(fsum<l && rsum>u){ for(int ptr=1;ptr<n-1-i;ptr++){ fsum+=w[I[ptr+i]]-w[I[ptr-1]]; if(l<=fsum && fsum<=u){ ans.assign(I.begin()+ptr,I.begin()+ptr+i+1); return ans; } } } } return vector<int>(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...