Submission #526375

#	Time	Username	Problem	Language	Result	Execution time	Memory
526375		Urvuk3	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	63 ms	5536 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll INF=1e9,LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(x) { cerr<<#x<<"="; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }

struct molecule{
    int idx,val;
};

bool cmp(molecule& a,molecule&b){
    return a.val<b.val;
}

vector<molecule> a;
vector<int> sol;

vector<int> find_subset(int l, int u, vector<int> w) {
    ll n=sz(w);
    a.resize(n);
    for(int i=0;i<n;i++){
        a[i].idx=i; a[i].val=w[i];
    }
    sort(all(a),cmp);
    int L=0,R=0;
    ll tmp=a[0].val;
    while(L<=R && L<n && R<n){
        if(l<=tmp && tmp<=u){
            for(int i=L;i<=R;i++) sol.pb(a[i].idx);
            return sol;
        }
        else if(tmp<l){
            if(R<n-1) tmp+=a[R+1].val;
            R++;
        }
        else{
            tmp-=a[L].val;
            L++;
        }
    }
    return std::vector<int>(0);
}

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