| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 362116 | Eyed | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int find_subset(int l, int u, int w[], int n, int result[]) {
int prefix[200005];
int suffix[200005];
bool less = false;
for (int i = 0; i < n; ++i) {
cin >> w[i];
if (w[i] >= l && w[i] <= u) {
result[0] = w[i];
return 1;
}
if (w[i] < l) less = true;
}
if (!less) {
cout << -1 << endl;
return 0;
}
sort(w, w + n);
//for (int i = 0; i < n; ++i) cout << w[i] << " ";
//cout << endl;
prefix[0] = w[0];
suffix[n - 1] = w[n - 1];
for (int i = 1; i < n; ++i) prefix[i] = prefix[i - 1] + w[i];
for (int i = n - 2; i >= 0; --i) suffix[i] = suffix[i + 1] + w[i];
if (prefix[n - 1] < l) {
return 0;
}
for (int i = 0; i < n; ++i) {
if (prefix[i] >= l && prefix[i] <= u) {
for (int j = 0; j <= i; ++j) result[j] = w[j];
return (i+1);
}
if (suffix[n - i - 1] >= l && suffix[n - i - 1] <= u) {
for (int j = n - 1; j >= n - i - 1; --j) result[n-1-j] = w[j];
return (i+1);
}
if (!(prefix[i] < l && suffix[n - i - 1] > u)) continue;
int curSum = prefix[i];
for (int j = 0; j <= min(i, n - i - 1); ++j) {
curSum += (w[n - j - 1] - w[j]);
if (curSum >= l && curSum <= u) {
for (int k = 0; k <= j; ++k) result[k] = w[n - k - 1];
for (int k = j + 1; k <= i; ++k) result[k] = w[k];
return (i + 1);
}
}
return 0;
}
return 0;
}