| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 378714 |
2021-03-17T03:30:49 Z |
syl123456 |
Gift (IZhO18_nicegift) |
C++17 |
|
489 ms |
103740 KB |
#include <bits/stdc++.h>
#define all(i) i.begin(), i.end()
#define rall(i) i.rbegin(), i.rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, int> pl;
ll gcd(ll i, ll j) {
if (j == 0) return i;
return i % j ? gcd(j, i % j) : j;
}
ll lcm(ll i, ll j) {
return i * j / gcd(i, j);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, k;
cin >> n >> k;
ll a[n], sum = 0, mx = 0;
priority_queue<pl> pq;
for (int i = 0; i < n; ++i) cin >> a[i], sum += a[i], mx = max(mx, a[i]), pq.emplace(a[i], i);
if (sum % k != 0 || mx > sum / k) return cout << -1, 0;
vector<int> v;
vector<vector<int>> ans;
while (sum > 0) {
for (int i = 0; i < k; ++i)
v.push_back(pq.top().second), pq.pop();
if (a[v.back()] == sum / k) {
ans.emplace_back(1, sum / k);
for (int i : v) ans.back().push_back(i + 1);
break;
}
ll x = min(a[v.back()], sum / k - pq.top().first);
//sum - kx >= ka[k]
ans.emplace_back(1, x);
while (!v.empty()) {
int i = v.back();
v.pop_back();
ans.back().push_back(i + 1);
a[i] -= x, sum -= x;
pq.emplace(a[i], i);
}
}
cout << ans.size() << '\n';
assert(~ans.empty());
for (auto i : ans) {
for (int j : i) cout << j << ' ', assert(j > 0);
cout << '\n';
}
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from nicegift.cpp:1:
nicegift.cpp: In function 'int main()':
nicegift.cpp:45:22: warning: '~' on an expression of type bool [-Wbool-operation]
45 | assert(~ans.empty());
| ~~~~~~~~~^~
nicegift.cpp:45:22: note: did you mean to use logical not ('!')?
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
n=4 |
| 2 |
Correct |
1 ms |
364 KB |
n=3 |
| 3 |
Correct |
1 ms |
364 KB |
n=3 |
| 4 |
Correct |
1 ms |
364 KB |
n=4 |
| 5 |
Correct |
1 ms |
364 KB |
n=4 |
| 6 |
Correct |
0 ms |
364 KB |
n=2 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
n=4 |
| 2 |
Correct |
1 ms |
364 KB |
n=3 |
| 3 |
Correct |
1 ms |
364 KB |
n=3 |
| 4 |
Correct |
1 ms |
364 KB |
n=4 |
| 5 |
Correct |
1 ms |
364 KB |
n=4 |
| 6 |
Correct |
0 ms |
364 KB |
n=2 |
| 7 |
Correct |
1 ms |
364 KB |
n=5 |
| 8 |
Correct |
1 ms |
364 KB |
n=8 |
| 9 |
Correct |
1 ms |
364 KB |
n=14 |
| 10 |
Correct |
1 ms |
364 KB |
n=11 |
| 11 |
Correct |
27 ms |
3560 KB |
n=50000 |
| 12 |
Correct |
24 ms |
3432 KB |
n=50000 |
| 13 |
Correct |
1 ms |
364 KB |
n=10 |
| 14 |
Correct |
1 ms |
364 KB |
n=685 |
| 15 |
Correct |
1 ms |
364 KB |
n=623 |
| 16 |
Correct |
1 ms |
364 KB |
n=973 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
n=4 |
| 2 |
Correct |
1 ms |
364 KB |
n=3 |
| 3 |
Correct |
1 ms |
364 KB |
n=3 |
| 4 |
Correct |
1 ms |
364 KB |
n=4 |
| 5 |
Correct |
1 ms |
364 KB |
n=4 |
| 6 |
Correct |
0 ms |
364 KB |
n=2 |
| 7 |
Correct |
1 ms |
364 KB |
n=5 |
| 8 |
Correct |
1 ms |
364 KB |
n=8 |
| 9 |
Correct |
1 ms |
364 KB |
n=14 |
| 10 |
Correct |
1 ms |
364 KB |
n=11 |
| 11 |
Correct |
27 ms |
3560 KB |
n=50000 |
| 12 |
Correct |
24 ms |
3432 KB |
n=50000 |
| 13 |
Correct |
1 ms |
364 KB |
n=10 |
| 14 |
Correct |
1 ms |
364 KB |
n=685 |
| 15 |
Correct |
1 ms |
364 KB |
n=623 |
| 16 |
Correct |
1 ms |
364 KB |
n=973 |
| 17 |
Correct |
1 ms |
364 KB |
n=989 |
| 18 |
Correct |
1 ms |
364 KB |
n=563 |
| 19 |
Correct |
1 ms |
364 KB |
n=592 |
| 20 |
Correct |
1 ms |
364 KB |
n=938 |
| 21 |
Correct |
1 ms |
364 KB |
n=747 |
| 22 |
Correct |
1 ms |
364 KB |
n=991 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
489 ms |
103740 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
n=4 |
| 2 |
Correct |
1 ms |
364 KB |
n=3 |
| 3 |
Correct |
1 ms |
364 KB |
n=3 |
| 4 |
Correct |
1 ms |
364 KB |
n=4 |
| 5 |
Correct |
1 ms |
364 KB |
n=4 |
| 6 |
Correct |
0 ms |
364 KB |
n=2 |
| 7 |
Correct |
1 ms |
364 KB |
n=5 |
| 8 |
Correct |
1 ms |
364 KB |
n=8 |
| 9 |
Correct |
1 ms |
364 KB |
n=14 |
| 10 |
Correct |
1 ms |
364 KB |
n=11 |
| 11 |
Correct |
27 ms |
3560 KB |
n=50000 |
| 12 |
Correct |
24 ms |
3432 KB |
n=50000 |
| 13 |
Correct |
1 ms |
364 KB |
n=10 |
| 14 |
Correct |
1 ms |
364 KB |
n=685 |
| 15 |
Correct |
1 ms |
364 KB |
n=623 |
| 16 |
Correct |
1 ms |
364 KB |
n=973 |
| 17 |
Correct |
1 ms |
364 KB |
n=989 |
| 18 |
Correct |
1 ms |
364 KB |
n=563 |
| 19 |
Correct |
1 ms |
364 KB |
n=592 |
| 20 |
Correct |
1 ms |
364 KB |
n=938 |
| 21 |
Correct |
1 ms |
364 KB |
n=747 |
| 22 |
Correct |
1 ms |
364 KB |
n=991 |
| 23 |
Runtime error |
489 ms |
103740 KB |
Execution killed with signal 6 |
| 24 |
Halted |
0 ms |
0 KB |
- |
