| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1062130 | Hectorungo_18 | 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;
mt19937 gnd(time(nullptr));
// #define int long long
vector<int> find_subset(int l, int r, vector<int> w){
int n = w.size();
vector<pair<int, int>> v(n);
for(int i = 0; i < n; i++){
v[i]={w[i], i};
}
sort(v.begin(), v.end());
int aux = 0;
vector<int> ba, bb;
for(int i = 0; i < n; i++){
ba[i]=v[i].first;
bb[i]=v[i].second;
}
vector<int> sol;
for(int i = n-1; i >= 0; i--){
if(ba[i] > r) continue;
sol.clear();
sol.push_back(bb[i]);
aux = ba[i];
bool im = 0;
int fal = l-aux;
int cp = i;
while(l > aux){
fal = r-aux;
auto it = upper_bound(ba.begin(), ba.begin()+cp, fal);
if(it == ba.begin()+cp || it == ba.begin()){
im = 0;
break;
}
else{
cp = it-ba.begin()-1;
aux+=ba[cp];
sol.push_back(bb[cp]);
}
if(aux >= l && aux <= r) break;
cp++;
if(cp == 0){
im = 0;
break;
}
}
if(im == 0) continue;
if(aux <= l && aux >= r) break;
}
if(aux < l || aux > r){
sol.clear();
}
return sol;
}
signed main() {
// ios::sync_with_stdio(false); cin.tie(nullptr);
while(1){
int n = gnd()%2000+3;
vector<int> v(n);
for(int i = 0; i < n; i++){
v[i]=gnd()%1000000+1;
}
sort(v.begin(), v.end());
int l = gnd()%1000000+1;
int r = gnd()%500000+1+v[n-1]-v[0]+l;
vector<int> a = find_subset(l, r, v), b = find(l, r, v);
if(min(a.size(), b.size()) == 0 && max(a.size(), b.size()) > 0){
cout << "FOUND " << endl;
cout << n << " " << l << " " << r << endl;
for(auto x : v) cout << x <<" ";
cout << endl;
for(auto x : a) cout << x <<" ";
cout << endl;
for(auto x : b) cout << x <<" ";
cout << endl;
return 0;
}
}
}