Submission #1109072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109072		hainam2k9	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	46 ms	7244 KiB

molecules

#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<ll,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;
    ll 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;
//int main()
//{
//    tt;
//    if(fopen((NAME + ".INP").c_str(), "r")) fo;
//    cin >> n >> l >> u;
//    vector<int> w(n,0);
//    for(int i = 0; i<n; ++i)
//        cin >> w[i];
//    find_subset(l,u,w);
//}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31