제출 #1001828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001828		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();
    int ansp = -1;
    vector<int> ans;
    vector<int> temp=arr;
    sort(all(arr));
    swap(l,u);
    set<pair<int,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;
        }

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

                int y = u - arr[i]; 
                auto it2 = var.lower_bound({y,{-1,-1}});
                if(it2!=var.end()){
                    if((*it2).first + arr[i]>=u &&(*it2).first<=l ){
                        int sumnow = arr[i]+ (*it).first;
                        var.ins({sumnow,{i,(*it).second.second}});
                        if(sumnow>=u && sumnow<=l){
                            ansp=sumnow;
                            idx=i;
                            break;
                        }
                    }
                }

            }
        }
        var.ins({arr[i],{i,i}});
    }

    
    // 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,{idx,-1}});
        need[arr[(*it).second.first]]++;
        sum+=arr[(*it).second.first];
        idx = (*it).second.second;
        var.erase(it);

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

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