Submission #942817

#	Time	Username	Problem	Language	Result	Execution time	Memory
942817		irmuun	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	424 KiB

molecules

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

vector<int>find_subset(int l,int u,vector<int>w){
    int n=(int)w.size();
    vector<pair<ll,int>>v(n);
    ll L=l,U=u,tot=0;
    for(int i=0;i<n;i++){
        v[i].ff=w[i];
        v[i].ss=i;
    }
    sort(all(v));
    int r=0;
    vector<int>ans;
    for(int i=0;i<n;i++){
        if(tot+v[i].ff<=u){
            tot+=v[i].ff;
            r=i+1;
            ans.pb(i);
        }
        else{
            break;
        }
    }
    if(r==0) return {};
    if(r==n&&tot<l) return {};
    if(l<=tot&&tot<=r){
        for(auto &x:ans){
            x=v[x].ss;
        }
        return ans;
    }
    ll curr=n-1;
    for(int i=(int)ans.size()-1;i>=0;i--){
        if(tot-v[ans[i]].ff+v[curr].ff<l){
            tot=tot-v[ans[i]].ff+v[curr].ff;
            ans[i]=curr;
            curr--;
        }
        else{
            for(int j=i+1;j<=curr;j++){
                tot=tot-v[ans[i]].ff+v[j].ff;
                ans[i]=j;
                if(l<=tot) break;
            }
            break;
        }
    }
    if(tot<l) return {};
    for(auto &x:ans){
        x=v[x].ss;
    }
    return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:15:8: warning: unused variable 'L' [-Wunused-variable]
   15 |     ll L=l,U=u,tot=0;
      |        ^
molecules.cpp:15:12: warning: unused variable 'U' [-Wunused-variable]
   15 |     ll L=l,U=u,tot=0;
      |            ^

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