제출 #1361094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361094		maya_s	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	27 ms	5288 KiB

molecules

#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

std::vector<int> find_subset(int L, int U, std::vector<int> W) {
   ll n = W.size(), l = L, u = U;
   vector<pll> w(n);
   for(ll i = 0; i < n; i++) w[i] = {W[i], i};
   sort(w.begin(), w.end());
   ll lo = 1, hi = n+1;
   vector<int> ans;
   while(lo < hi){
    ll k = (lo + hi) / 2, s = 0;
    for(ll i = 0; i < k; i++) s += w[i].first;
    if(s > u) {hi = k; continue;}
    if(s >= l) {
        for(ll j = 0; j < k; j++) ans.push_back(w[j].second);
        break;
    }
    for(ll i = k; i < n; i++){
        s -= w[i-k].first; s += w[i].first;
        if(s >= l){
            for(ll j = i-k+1; j <= i; j++) ans.push_back(w[j].second);
            break;
        }
    }
    if(ans.size()) break;
    lo = k+1;
   }
   return ans;
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 10 / 10
• 서브태스크 3: 12 / 12
• 서브태스크 4: 15 / 15
• 서브태스크 5: 23 / 23
• 서브태스크 6: 31 / 31