Submission #1109068

#TimeUsernameProblemLanguageResultExecution timeMemory
1109068hainam2k9Detecting Molecules (IOI16_molecules)C++17
69 / 100
3 ms760 KiB
#include <bits/stdc++.h>
//#include <molecules.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "";
vector<int> find_subset(int l, int u, vector<int> w){
    int n=sz(w);
    pair<int,int> p[n];
    for(int i = 0; i<n; ++i)
        p[i].fi=w[i], p[i].se=i;
    sort(p,p+n);
    deque<int> dq;
    vector<int> result;
    int sum=0;
    for(int i = 0; i<n; ++i){
        sum+=p[i].fi, dq.pb(i);
        if(sum<l){
            int pos=lb(p+i+1,p+n,make_pair(l-sum,0))-p;
            if(pos>i&&pos<n&&sum+p[pos].fi<=u){
                dq.pb(pos);
                for(int i = 0; i<sz(dq); ++i)
                    result.pb(p[dq[i]].se);
                return result;
            }
        }
        while(sum>u) sum-=p[dq.front()].fi, dq.pof();
        if(sum>=l&&sum<=u){
            for(int i = 0; i<sz(dq); ++i)
                result.pb(p[dq[i]].se);
            return result;
        }
    }
    return vector<int>(0);
}
//int n,l,u,w[105],result[105];
//int main()
//{
//    tt;
//    if(fopen((NAME + ".INP").c_str(), "r")) fo;
//    cin >> n >> l >> u;
//    for(int i = 0; i<n; ++i)
//        cin >> w[i];
//    cout << find_subset(l,u,w,n,result);
//}
#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...