Submission #1163104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163104		8pete8	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	40 ms	13740 KiB

molecules

#include "molecules.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define f first
#define s second
vector<int32_t> find_subset(int32_t l, int32_t u, vector<int32_t> w){
    vector<pii>have;
    int sum=0;
    for(int i=0;i<w.size();i++)have.pb({w[i],i});
    sort(all(have));
    int i=0;
    vector<int32_t>ans;
    vector<int>on(w.size(),0);
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    for(;i<have.size();i++){
        if(sum+have[i].f>l){
            if(sum+have[i].f<=u){
                ans.pb(have[i].s);
                return ans;
            }
            break;
        }
        sum+=have[i].f;
        ans.pb(have[i].s);
        pq.push({have[i].f,have[i].s});
        on[have[i].s]=1;
    }
    if(sum==l)return ans;
    ans.clear();
    if(i==0)return ans;
    while(i<have.size()&&sum<l){
        while(!pq.empty()&&!on[pq.top().s])pq.pop();
        sum+=(have[i].f-pq.top().f);
        on[pq.top().s]=0;
        on[have[i].s]=1;
        pq.push({have[i].f,have[i].s});
        pq.pop();
        i++;
    }
    if(sum<l)return ans;
    while(!pq.empty())ans.pb(pq.top().s),pq.pop();
    sort(all(ans));
    return ans;
}

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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