Submission #1163398

#TimeUsernameProblemLanguageResultExecution timeMemory
1163398AzaDetecting Molecules (IOI16_molecules)C++20
9 / 100
0 ms328 KiB
//AzaLE (Azamat Alisherov) #include <bits/stdc++.h> #include "molecules.h" #define F first #define S second #define size(x) (int)x.size() using namespace std; vector <int> find_subset(int l, int r, vector<int> v){ set<pair<int, int>> st; //using set so no two identical values appear while searching within L and R //st.F is value; //st.S is index; vector <int> inds(size(v)); //using this vector to retrieve answer if it exists- //-via backtracking indexes st.insert({0, -1}); for(int i = 0; i < size(v); i++){ int mn = l - v[i]; //searching for appropriate minimum "adder" for L; auto it = st.lower_bound({mn, 0}); if(it == st.end())it--; //cout << v[i] << "----> " << mn << " " << (*it).F << " " << (*it).S << endl; pair<int, int> ins; ins.F = (*it).F + v[i]; inds[i] = (*it).S; ins.S = i; st.insert({v[i], i}); if(ins.F > r)continue; st.insert(ins); } //for(auto [a, b]:st)cout << a << " " << b << endl; auto it = st.lower_bound({l, -1}); int stind = -1; //stind (starting index) to backtrack the answer if((*it).F >= l and (*it).F <= r){ stind = (*it).S; } for(int i = 0; i < size(v); i++){ if(v[i] >= l and v[i] <= r){ return {i}; } } if(stind == -1){ return {}; } vector <int> ans; while(stind >= 0){ ans.push_back(stind); stind = inds[stind]; } int res = 0; for(int i = 0; i < size(ans); i++){ res += v[ans[i]]; } while(res > r){ res -= v[ans.back()]; ans.pop_back(); } return ans; } /* */

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...