QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#494282 | #3025. Assimilation | PetroTarnavskyi# | AC ✓ | 172ms | 13680kb | C++20 | 1.3kb | 2024-07-27 15:01:11 | 2024-07-27 15:01:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
void solve()
{
int n;
LL s;
cin >> n >> s;
VI a(n);
FOR (i, 0, n)
cin >> a[i];
multiset<LL> free(ALL(a));
int ans = 0;
multiset<LL> capt;
auto it = free.upper_bound(s);
while (it != free.end())
{
if (it == free.begin())
{
cout << -1 << '\n';
return;
}
it--;
s += *it;
ans++;
free.erase(it);
it = free.upper_bound(s);
}
it--;
s -= *it;
capt.insert(*it);
free.erase(it);
while (!free.empty())
{
it = free.upper_bound(s);
if (it == free.begin())
{
s += 2 * *capt.rbegin();
ans++;
capt.erase(prev(capt.end()));
it = free.upper_bound(s);
assert(it != free.begin());
}
it--;
s -= *it;
capt.insert(*it);
free.erase(it);
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 172ms
memory: 13680kb
input:
29 9 1 1 1 2 1 1 1 1 1 1 4 1 3 2 1 1 5 316660370 269357435 105688553 346785866 295093544 181703417 6 43402885 39947441 27068237 43810814 44913378 40095941 34779892 22 319594 3815194 3056481 6593888 7315914 6593888 4794774 2561877 5256242 4920603 5256242 3606645 864746 1594265 1235578 2361430 2277526...
output:
4 2 2 3 -1 10621 4 -1 7 5385 8 2 -1 5 6264 3 0 -1 124764 5 -1 7 10940 1 3 100000 5 -1 -1
result:
ok 29 lines
Test #2:
score: 0
Accepted
time: 167ms
memory: 13680kb
input:
30 1537 2 5 6 3 3 6 5 3 5 5 5 6 5 5 6 4 6 6 6 4 3 5 5 5 6 4 6 2 3 4 5 5 5 5 5 6 6 6 4 4 4 2 6 6 5 3 6 5 6 6 5 6 5 4 3 5 6 4 3 5 3 6 4 5 6 4 1 4 6 4 5 2 4 3 4 6 6 5 5 5 6 6 5 5 5 6 4 5 6 6 6 5 5 5 3 3 2 4 6 3 5 4 4 6 6 6 5 5 6 4 4 6 6 6 6 4 6 6 3 4 5 5 3 4 5 4 6 5 5 6 5 6 6 3 3 6 5 4 6 4 6 6 4 5 3 2 ...
output:
629 22 1452 10 2121 5094 6 1135 7123 2140 4 916 1802 1237 5 6 1498 262 115823 1223 11 1032 844 13 1899 4 1212 17 -1 1797
result:
ok 30 lines
Test #3:
score: 0
Accepted
time: 147ms
memory: 12004kb
input:
30 11 40454552 9677001 192936684 252254034 192936684 37357273 9156546 74500194 116624778 13650360 2174119 13650360 27 1 3 2 3 1 3 5 3 5 1 1 1 1 1 1 4 4 1 1 1 2 1 3 3 1 3 2 4 11 72578887 172937772 206562668 87600829 84557056 103901588 148396091 92438037 215698807 125600579 216304481 191851963 5 1 1 2...
output:
4 9 -1 3 19 -1 5 9 4 4 18 14 5 5 83242 7 4 -1 6 22 5 3 17 -1 2 7 22 158159 -1 12
result:
ok 30 lines