Submission #1028960

#TimeUsernameProblemLanguageResultExecution timeMemory
1028960c2zi6Detecting Molecules (IOI16_molecules)C++14
100 / 100
41 ms7120 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #include "molecules.h" /*const int MAXN = 1e4;*/ /*const int MAXSUM = 1e4;*/ /*bitset<MAXSUM+1> dp[MAXN+1];*/ /*VI find_subset(int L, int R, VI w) {*/ /* dp[0][0] = true;*/ /* int n = w.size();*/ /* rep(i, n) replr(s, 0, MAXSUM) {*/ /* dp[i+1] = dp[i] | (dp[i]<<w[i]);*/ /* }*/ /* replr(s, L, R) if (dp[n][s]) {*/ /* VI ret;*/ /* ret.reserve(n);*/ /* reprl(i, n-1, 0) {*/ /* if (!dp[i][s]) {*/ /* s -= w[i];*/ /* ret.pb(i);*/ /* }*/ /* }*/ /* return ret;*/ /* }*/ /* return VI{};*/ /*}*/ VI find_subset(int L, int R, VI w) { int n = w.size(); VI ind(n); {// sort VPI tmp; rep(i, n) tmp.pb({w[i], i}); sort(all(tmp)); rep(i, n) { w[i] = tmp[i].ff; ind[i] = tmp[i].ss; } } sort(all(w)); ll l = 0, r = 0; replr(k, 1, n) {// how many numbers are taken l += w[k-1]; r += w[n-k]; if (R < l || L > r) continue; /*cout << "INTERSECTED WITH " << l << " " << r << endl;*/ /*cout << "SET MUST CONTAIN " << k << " ELEMENTS" << endl;*/ VI ans(n); rep(i, k) ans[i] = true; ll cur = l; if (cur >= L); else rep(i, k) { cur -= w[i]; cur += w[n-1-i]; ans[i] = false; ans[n-1-i] = true; if (cur >= L) break; } VI ret; rep(i, n) if (ans[i]) ret.pb(ind[i]); return ret; } return VI{}; }
#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...