# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
572875 |
2022-06-05T12:18:33 Z |
vovamr |
Gift (IZhO18_nicegift) |
C++17 |
|
2000 ms |
125960 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
inline void solve() {
ll n, k;
cin >> n >> k;
ve<ll> a(n);
ll s = 0;
set<pll> st;
for (int i = 0; i < n; ++i) {
cin >> a[i];
st.insert({a[i], i});
s += a[i];
}
if (s % k || (*st.rbegin()).fi > s / k) return void(cout << -1);
ve<pair<ll,ve<int>>> answer;
while (sz(st)) {
ve<pll> ind;
for (int i = 0; i < k; ++i) {
ind.pb(*--st.end());
st.erase(--st.end());
}
ll add = ind.back().fi;
if (sz(st)) chmin(add, s / k - (*--st.end()).fi);
answer.pb({add, {}});
for (auto &[_, i] : ind) {
s -= add, a[i] -= add;
if (a[i]) st.insert({a[i], i});
answer.back().se.pb(i);
}
}
cout << sz(answer) << '\n';
for (auto &[add, vec] : answer) {
cout << add << " ";
for (auto i : vec) cout << i + 1 << " ";
cout << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
n=4 |
2 |
Correct |
0 ms |
212 KB |
n=3 |
3 |
Correct |
0 ms |
212 KB |
n=3 |
4 |
Correct |
0 ms |
212 KB |
n=4 |
5 |
Correct |
0 ms |
212 KB |
n=4 |
6 |
Correct |
0 ms |
212 KB |
n=2 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
n=4 |
2 |
Correct |
0 ms |
212 KB |
n=3 |
3 |
Correct |
0 ms |
212 KB |
n=3 |
4 |
Correct |
0 ms |
212 KB |
n=4 |
5 |
Correct |
0 ms |
212 KB |
n=4 |
6 |
Correct |
0 ms |
212 KB |
n=2 |
7 |
Correct |
0 ms |
212 KB |
n=5 |
8 |
Correct |
0 ms |
212 KB |
n=8 |
9 |
Correct |
0 ms |
212 KB |
n=14 |
10 |
Correct |
0 ms |
212 KB |
n=11 |
11 |
Correct |
27 ms |
5472 KB |
n=50000 |
12 |
Correct |
23 ms |
5196 KB |
n=50000 |
13 |
Correct |
0 ms |
212 KB |
n=10 |
14 |
Correct |
1 ms |
340 KB |
n=685 |
15 |
Correct |
1 ms |
340 KB |
n=623 |
16 |
Correct |
1 ms |
340 KB |
n=973 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
n=4 |
2 |
Correct |
0 ms |
212 KB |
n=3 |
3 |
Correct |
0 ms |
212 KB |
n=3 |
4 |
Correct |
0 ms |
212 KB |
n=4 |
5 |
Correct |
0 ms |
212 KB |
n=4 |
6 |
Correct |
0 ms |
212 KB |
n=2 |
7 |
Correct |
0 ms |
212 KB |
n=5 |
8 |
Correct |
0 ms |
212 KB |
n=8 |
9 |
Correct |
0 ms |
212 KB |
n=14 |
10 |
Correct |
0 ms |
212 KB |
n=11 |
11 |
Correct |
27 ms |
5472 KB |
n=50000 |
12 |
Correct |
23 ms |
5196 KB |
n=50000 |
13 |
Correct |
0 ms |
212 KB |
n=10 |
14 |
Correct |
1 ms |
340 KB |
n=685 |
15 |
Correct |
1 ms |
340 KB |
n=623 |
16 |
Correct |
1 ms |
340 KB |
n=973 |
17 |
Correct |
1 ms |
340 KB |
n=989 |
18 |
Correct |
1 ms |
340 KB |
n=563 |
19 |
Correct |
1 ms |
340 KB |
n=592 |
20 |
Correct |
1 ms |
340 KB |
n=938 |
21 |
Correct |
1 ms |
340 KB |
n=747 |
22 |
Correct |
1 ms |
340 KB |
n=991 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
642 ms |
101012 KB |
n=1000000 |
2 |
Correct |
400 ms |
64332 KB |
n=666666 |
3 |
Correct |
228 ms |
37876 KB |
n=400000 |
4 |
Correct |
153 ms |
26828 KB |
n=285714 |
5 |
Correct |
9 ms |
2132 KB |
n=20000 |
6 |
Correct |
110 ms |
17076 KB |
n=181818 |
7 |
Correct |
6 ms |
1196 KB |
n=10000 |
8 |
Correct |
5 ms |
852 KB |
n=6666 |
9 |
Correct |
2 ms |
596 KB |
n=4000 |
10 |
Correct |
5 ms |
596 KB |
n=2857 |
11 |
Correct |
3 ms |
468 KB |
n=2000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
n=4 |
2 |
Correct |
0 ms |
212 KB |
n=3 |
3 |
Correct |
0 ms |
212 KB |
n=3 |
4 |
Correct |
0 ms |
212 KB |
n=4 |
5 |
Correct |
0 ms |
212 KB |
n=4 |
6 |
Correct |
0 ms |
212 KB |
n=2 |
7 |
Correct |
0 ms |
212 KB |
n=5 |
8 |
Correct |
0 ms |
212 KB |
n=8 |
9 |
Correct |
0 ms |
212 KB |
n=14 |
10 |
Correct |
0 ms |
212 KB |
n=11 |
11 |
Correct |
27 ms |
5472 KB |
n=50000 |
12 |
Correct |
23 ms |
5196 KB |
n=50000 |
13 |
Correct |
0 ms |
212 KB |
n=10 |
14 |
Correct |
1 ms |
340 KB |
n=685 |
15 |
Correct |
1 ms |
340 KB |
n=623 |
16 |
Correct |
1 ms |
340 KB |
n=973 |
17 |
Correct |
1 ms |
340 KB |
n=989 |
18 |
Correct |
1 ms |
340 KB |
n=563 |
19 |
Correct |
1 ms |
340 KB |
n=592 |
20 |
Correct |
1 ms |
340 KB |
n=938 |
21 |
Correct |
1 ms |
340 KB |
n=747 |
22 |
Correct |
1 ms |
340 KB |
n=991 |
23 |
Correct |
642 ms |
101012 KB |
n=1000000 |
24 |
Correct |
400 ms |
64332 KB |
n=666666 |
25 |
Correct |
228 ms |
37876 KB |
n=400000 |
26 |
Correct |
153 ms |
26828 KB |
n=285714 |
27 |
Correct |
9 ms |
2132 KB |
n=20000 |
28 |
Correct |
110 ms |
17076 KB |
n=181818 |
29 |
Correct |
6 ms |
1196 KB |
n=10000 |
30 |
Correct |
5 ms |
852 KB |
n=6666 |
31 |
Correct |
2 ms |
596 KB |
n=4000 |
32 |
Correct |
5 ms |
596 KB |
n=2857 |
33 |
Correct |
3 ms |
468 KB |
n=2000 |
34 |
Correct |
21 ms |
3280 KB |
n=23514 |
35 |
Correct |
29 ms |
3144 KB |
n=23514 |
36 |
Correct |
1 ms |
468 KB |
n=940 |
37 |
Correct |
1 ms |
212 KB |
n=2 |
38 |
Correct |
68 ms |
9204 KB |
n=100000 |
39 |
Correct |
56 ms |
9144 KB |
n=100000 |
40 |
Correct |
1 ms |
212 KB |
n=10 |
41 |
Correct |
1 ms |
340 KB |
n=100 |
42 |
Correct |
4 ms |
468 KB |
n=1000 |
43 |
Correct |
795 ms |
116168 KB |
n=1000000 |
44 |
Execution timed out |
2025 ms |
125960 KB |
Time limit exceeded |
45 |
Halted |
0 ms |
0 KB |
- |