| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 761927 | AirCircles | Detecting Molecules (IOI16_molecules) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<long long> vec;
typedef long long ll;
vec find_subset(ll l, ll u, vec w ){
int n=w.size();
vec dm(0);
vector<pair<ll,ll> >dn(n);
for(int i=0;i<n;i++){
dn[i].first=w[i];
dn[i].second=i;
}
sort(dn.begin(),dn.end());
vec mi(n),mx(n);
mi[0]=dn[0].first;
mx[0]=dn[n-1].first;
for(int i=1;i<n;i++){
mi[i]=mi[i-1]+dn[i].first;
mx[i]=mx[i-1]+dn[n-1-i].first;
}
for(int i=0;i<n;i++){
if(mi[i]>u||mx[i]<l){
if(mx[i]<l){
continue;
}else{
dm.resize(1,0);
break;
}
}else{
ll k=mi[i];
int kk=n;
for(int j=0;j<n;j++){
if(k>=l){
kk=j;
break;
}else{
k+=dn[n-1-j].first-dn[j].first;
}
}
for(int j=kk;j<=i;j++){
dm.push_back(dn[j].second);
}
for(int j=n-1;j>=n-kk;j--){
dm.push_back(dn[j].second);
}
break;
}
}
return dm;
}