| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1068329 | quangminh412 | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
/*
John Watson
https://codeforces.com/profile/quangminh98
Mua Code nhu mua Florentino !!
*/
#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
const int oo = 1e9;
vector<int> solve_1(int l, int u, vector<int> w)
{
vector<int> ans;
int cur = 0;
for (int i = 0; i < w.size(); i++)
{
cur += w[i];
ans.push_back(i);
if (l <= cur && cur <= u)
return ans;
}
return {};
}
vector<int> solve_2(int l, int u, vector<int> w)
{
vector<pair<int, int>> c1, c2;
for (int i = 0; i < w.size(); i++)
{
if (w[i] == w[0])
c1.push_back(make_pair(w[i], i));
else
c2.push_back(make_pair(w[i], i));
}
int cur = 0;
vector<int> ans;
for (int i = 0; i < c1.size(); i++)
{
ans.push_back(c1[i].second);
cur += c1[i].first;
if (l <= sum && sum <= u)
return ans;
}
cur = 0;
ans.clear();
for (int i = 0; i < c2.size(); i++)
{
ans.push_back(c2[i].second);
cur += c2[i].first;
if (l <= sum && sum <= u)
return ans;
}
for (int i = 0; i < c1.size(); i++)
for (int j = 0; j < c2.size(); j++)
{
vector<int> ans;
int sum = 0;
for (int k = 0; k <= i; k++) ans.push_back(c1[k].second), sum += c1[k].first;
for (int k = 0; k <= j; k++) ans.push_back(c2[k].second), sum += c2[k].first;
if (l <= sum && sum <= u)
return ans;
}
return {};
}
vector<int> find_subset(int l, int u, vector<int> w)
{
// sub1
bool sub1 = true;
for (int i = 1; i < w.size(); i++)
if (w[i] != w[i - 1])
sub1 = false;
if (sub1 == true)
return solve_1(l, u, w);
// sub2
int mn = oo, mx = 0;
for (int i = 1; i < w.size(); i++)
{
mn = min(mn, w[i]);
mx = max(mx, w[i]);
}
if (mx - mn <= 1)
return solve_2(l, u, w);
// sub3
}