| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 88358 | amiratou | 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 <cstdio>
#include <vector>
#include <cassert>
#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#include "molecules.h"
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
using namespace std;
#include "molecules.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
vector<int> ans;
vector<pair<int,int> > vec;
void process(int j,int i){
for (int idx = j; idx <= i ; ++idx)
ans.push_back(vec[idx].se);
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
vec.resize(w.size());
for (int i = 0; i < w.size(); ++i)
{
vec[i].fi=w[i];
vec[i].se=i;
}
sort(vec.begin(),vec.end());
if(vec[0].fi>=l&&vec[0].fi<=u){
process(0,0);
return ans;
}
for (int i = 1; i < w.size(); ++i){
vec[i].fi+=vec[i-1].fi;
if(vec[i].fi>=l&&vec[i].fi<=u){
process(0,i);
return ans;
}
}
/*cout<<"\n";
for (int i = 0; i < w.size(); ++i)
{
cout<<vec[i].fi<<" ";
}
cout<<"\n";*/
for (int i = 0; i < w.size(); ++i)
{
if(vec[i].fi>u){
auto search=lower_bound(vec.begin(),vec.begin()+i,make_pair(vec[i].fi-l,0));
//debugs(vec[i].fi,search-vec.begin());
if(search==vec.begin()+i) continue;
//debugs(vec[i].fi-l,(vec[i].fi-search->fi));
if(search->fi!=vec[i].fi-l){
if(search->fi>vec[i].fi-l&&search!=vec.begin())
search--;
}
if((vec[i].fi-search->fi)>=l&&(vec[i].fi-search->fi)<=u){
process((search-vec.begin())+1,i);
return ans;
}
}
}
return vector<int>(0);
}
int main() {
int n, l, u;
assert(3 == scanf("%d %d %d", &n, &l, &u));
std::vector<int> w(n);
for (int i = 0; i < n; i++)
assert(1 == scanf("%d", &w[i]));
std::vector<int> result = find_subset(l, u, w);
printf("%d\n", (int)result.size());
for (int i = 0; i < (int)result.size(); i++)
printf("%d%c", result[i], " \n"[i == (int)result.size() - 1]);
}