| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 778180 | vjudge1 | Detecting Molecules (IOI16_molecules) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 8e5+37;
#include <cstdio>
#include <vector>
#include <cassert>
#include "molecules.h"
void f(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
vector<long long> find_subset(long long l, long long u, vector<long long> w) {
long long n= w.size();
vector<array<long long, 2>> a(n);
vector<long long> vis(n);
for(long long i=0; i<n; i++){
a[i]={w[i], i};
}
sort(a.begin(), a.end());
if(a[0][0]>u)
return vector<long long>(0);
vector<array<long long, 2>> pff;
long long sum=0, k=-1;
for(long long i=0; i<n&&k==-1; i++){
if(sum+a[i][0]>=l){
k=i;
}
else{
sum+=a[i][0];
vis[i]=1;
}
}
if(k==-1) return std::vector<long long>(0);
if(k==0){
vector<long long> ans(1);
ans[0]=a[0][1];
return ans;
}
if(sum+a[k][0]>=l&&sum+a[k][0]<=u){
vector<long long> ans;
for(long long i=0; i<=k; i++) ans.push_back(a[i][1]);
return ans;
}
long long p=n-1;
for(long long i=0; i<k&&2*i<p; i++){
sum+=a[p-i][0]-a[i][0];
vis[p-i]=1; vis[i] = 0;
if(sum>=l) break;
}
if(sum<l||sum>u) return std::vector<long long>(0);
vector<long long> ans;
for(long long i=0; i<n; i++){
if(vis[i]==1)
ans.push_back(a[i][1]);
}
sort(ans.begin(), ans.end());
return ans;
}