Submission #714485

#TimeUsernameProblemLanguageResultExecution timeMemory
714485europiumDetecting Molecules (IOI16_molecules)C++17
0 / 100
1 ms304 KiB
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <numeric> #include <cmath> #include<iterator> #include <set> #include <map> #include <math.h> #include <iomanip> #include <unordered_set> #include <queue> #include <climits> #include "molecules.h" using namespace std; vector<int> ps; int sum(int l, int r){ return ps[r + 1] - ps[l]; } vector<int> find_subset(int a, int b, vector<int> w) { int n = w.size(); ps.resize(n + 1); vector<pair<int,int>> pos(n); for (int i = 0; i < n; i++){ pos[i].first = w[i]; pos[i].second = i; } sort(pos.begin(), pos.end()); // init ps for (int i = 0; i < n; i++){ ps[i + 1] = ps[i] + pos[i].first; } for (int k = 0; k < n; k++){ int l = 0, r = n - k, mid, wsum; // cout << l << ' ' << r << '\n'; do { mid = l + (r - l + 1) / 2; // cout << mid << '\n'; wsum = sum(mid, mid + k); // cout << k << ' ' << wsum << '\n'; if (wsum < a) r = mid - 1; else if (wsum > b) l = mid; else { vector<int> ans; for (int j = mid; j <= mid + k; j++) ans.push_back(pos[j].second); return ans; } } while (l < r); } 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...