Submission #937083

#TimeUsernameProblemLanguageResultExecution timeMemory
937083ThegeekKnight16Detecting Molecules (IOI16_molecules)C++17
100 / 100
41 ms8004 KiB
#include <bits/stdc++.h> using namespace std; #include "molecules.h" typedef long long ll; std::vector<int> find_subset(int l, int u, std::vector<int> w) { int N = w.size(); vector<int> id(N); iota(id.begin(), id.end(), 0); sort(id.begin(), id.end(), [&](const int &a, const int &b) {return w[a] < w[b];}); vector<ll> minI(N+1), maxI(N+1); for (int i = 1; i <= N; i++) minI[i] = minI[i-1] + (ll)w[id[i-1]], maxI[i] = maxI[i-1] + (ll)w[id[N-i]]; for (int i = 1; i <= N; i++) { if (maxI[i] < l || minI[i] > u) continue; if (l <= minI[i] && minI[i] <= u) { vector<int> resp(i); for (int j = 0; j < i; j++) resp[j] = id[j]; return resp; } if (l <= maxI[i] && maxI[i] <= u) { vector<int> resp(i); for (int j = 0; j < i; j++) resp[j] = id[N-1-j]; return resp; } ll S = minI[i]; int j = 0; while (S < l) { S += (ll)w[id[N-1-j]] - (ll)w[id[j]]; ++j; } vector<int> resp; for (int k = j; k < i; k++) resp.push_back(id[k]); for (int k = 0; k < j; k++) resp.push_back(id[N-1-k]); return resp; } 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...