Submission #1001778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001778		vjudge1	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	1 ms	348 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
vector<int> find_subset(int l, int u, vector<int> arr) {
    int n = arr.size();
    vector<int> parent(n,-1);
    int ansp = -1;
    vector<int> ans;
    vector<int> temp=arr;
    sort(all(arr));
    swap(l,u);
    set<pair<int,int>> var;
    int idx =0; 
    for(int i=0;i<n;i++){
        // cout<<arr[i]<<endl;
        if(arr[i]>l){
            continue;
        }

        if(arr[i]>=u){
            for(int j=0;j<n;j++){
                if(temp[j]==arr[i]){
                    ans.pb(j);
                    break;
                }
            }
            return ans;
        }

        int x = l-arr[i];
        auto it = var.upper_bound({x,-1});
        // cout<<arr[i]<<"  ucun it search"<<endl;
        if(it!=var.begin()){
            --it;
            // cout<<arr[i]<<" buldum "<<(*it).second<<endl;
            int sumnow = arr[i]+ (*it).first;
            // cout<<sumnow<<endl;
            parent[i]=(*it).second;
            var.ins({sumnow,i});
            if(sumnow>=u && sumnow<=l){
                ansp=i;
                ansp=sumnow;
                idx=i;
                break;
            }
        }

        var.ins({arr[i],i});
        // cout<<arr[i]<<" insertledim"<<endl;
    }

    
    // reverse(all(ans));
    map<int,int> need;
    vector<int> ans2;
    int sum=0;
    if(ansp==-1){
        return ans2;
    }
    int tmp=ansp;
    set<int> used;
    while(!(sum>=u && sum<=l)){
        // cout<<sum<<endl;
        auto it = var.lower_bound({tmp-sum,-1});
        need[arr[(*it).second]]++;
        sum+=arr[(*it).second];
        var.erase(it);

    }
    
    for(int i=0;i<n;i++){
        if(need[temp[i]]){
            ans2.pb(i);
            need[temp[i]]--;
        }
    }
    return ans2;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:19:9: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
   19 |     int idx =0;
      |         ^~~

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