Submission #21176

#TimeUsernameProblemLanguageResultExecution timeMemory
21176sbansalcsDetecting Molecules (IOI16_molecules)C++14
100 / 100
79 ms6988 KiB
#include "molecules.h" #include <algorithm> #include <assert.h> #include <iostream> typedef long long ll; using namespace std; const int N = 2e5+5; pair<int,int> arr[N]; ll sums[N]; std::vector<int> find_subset(int l, int u, std::vector<int> w) { vector<int> ans; int n=w.size(); for(int i=1;i<=n;i++) { arr[i].first=w[i-1]; arr[i].second=i-1; } sort(arr+1,arr+1+n); for(int i=1;i<=n;i++) { if(arr[i].first>=l && arr[i].first<=u) { ans.push_back(arr[i].second); return ans; } sums[i]=sums[i-1]+arr[i].first; } int k=0; if(sums[n]>=l && sums[n]<=u) { for(int i=0;i<n;i++) { ans.push_back(i); } return ans; } for(int i=2;i<n;i++) { if(sums[i]>u || sums[n]-sums[n-i]<l) continue; if(sums[n]-sums[n-i]<=u) { for(int j=n-i+1;j<=n;j++) { ans.push_back(arr[j].second); } return ans; } int lx=1,rx=i; ll sm=sums[i]; if(sm>=l && sm<=u) { for(int j=lx;j<=rx;j++) { ans.push_back(arr[j].second); } break; } while(rx<n) { sm-=arr[lx].first;lx++; rx++; sm+=arr[rx].first; if(sm>=l && sm<=u) { for(int j=lx;j<=rx;j++) { ans.push_back(arr[j].second); } break; } } break; } return ans; }

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:25:6: warning: unused variable 'k' [-Wunused-variable]
  int k=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...