| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 572864 |
2022-06-05T12:13:03 Z |
vovamr |
Gift (IZhO18_nicegift) |
C++17 |
|
253 ms |
51256 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() {
int n, k;
cin >> n >> k;
ve<int> a(n);
ll s = 0;
set<pii> 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<int,ve<int>>> answer;
while (sz(st)) {
ve<pii> 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 |
1 ms |
212 KB |
n=4 |
| 2 |
Correct |
1 ms |
212 KB |
n=3 |
| 3 |
Correct |
0 ms |
324 KB |
n=3 |
| 4 |
Correct |
0 ms |
324 KB |
n=4 |
| 5 |
Correct |
0 ms |
284 KB |
n=4 |
| 6 |
Correct |
0 ms |
212 KB |
n=2 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n=4 |
| 2 |
Correct |
1 ms |
212 KB |
n=3 |
| 3 |
Correct |
0 ms |
324 KB |
n=3 |
| 4 |
Correct |
0 ms |
324 KB |
n=4 |
| 5 |
Correct |
0 ms |
284 KB |
n=4 |
| 6 |
Correct |
0 ms |
212 KB |
n=2 |
| 7 |
Correct |
0 ms |
212 KB |
n=5 |
| 8 |
Correct |
1 ms |
328 KB |
n=8 |
| 9 |
Correct |
0 ms |
212 KB |
n=14 |
| 10 |
Correct |
1 ms |
212 KB |
n=11 |
| 11 |
Correct |
26 ms |
4420 KB |
n=50000 |
| 12 |
Correct |
28 ms |
4220 KB |
n=50000 |
| 13 |
Correct |
1 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 |
1 ms |
212 KB |
n=4 |
| 2 |
Correct |
1 ms |
212 KB |
n=3 |
| 3 |
Correct |
0 ms |
324 KB |
n=3 |
| 4 |
Correct |
0 ms |
324 KB |
n=4 |
| 5 |
Correct |
0 ms |
284 KB |
n=4 |
| 6 |
Correct |
0 ms |
212 KB |
n=2 |
| 7 |
Correct |
0 ms |
212 KB |
n=5 |
| 8 |
Correct |
1 ms |
328 KB |
n=8 |
| 9 |
Correct |
0 ms |
212 KB |
n=14 |
| 10 |
Correct |
1 ms |
212 KB |
n=11 |
| 11 |
Correct |
26 ms |
4420 KB |
n=50000 |
| 12 |
Correct |
28 ms |
4220 KB |
n=50000 |
| 13 |
Correct |
1 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 |
328 KB |
n=592 |
| 20 |
Correct |
1 ms |
340 KB |
n=938 |
| 21 |
Correct |
1 ms |
340 KB |
n=747 |
| 22 |
Correct |
1 ms |
324 KB |
n=991 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
253 ms |
51256 KB |
Jury has the answer but participant has not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n=4 |
| 2 |
Correct |
1 ms |
212 KB |
n=3 |
| 3 |
Correct |
0 ms |
324 KB |
n=3 |
| 4 |
Correct |
0 ms |
324 KB |
n=4 |
| 5 |
Correct |
0 ms |
284 KB |
n=4 |
| 6 |
Correct |
0 ms |
212 KB |
n=2 |
| 7 |
Correct |
0 ms |
212 KB |
n=5 |
| 8 |
Correct |
1 ms |
328 KB |
n=8 |
| 9 |
Correct |
0 ms |
212 KB |
n=14 |
| 10 |
Correct |
1 ms |
212 KB |
n=11 |
| 11 |
Correct |
26 ms |
4420 KB |
n=50000 |
| 12 |
Correct |
28 ms |
4220 KB |
n=50000 |
| 13 |
Correct |
1 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 |
328 KB |
n=592 |
| 20 |
Correct |
1 ms |
340 KB |
n=938 |
| 21 |
Correct |
1 ms |
340 KB |
n=747 |
| 22 |
Correct |
1 ms |
324 KB |
n=991 |
| 23 |
Incorrect |
253 ms |
51256 KB |
Jury has the answer but participant has not |
| 24 |
Halted |
0 ms |
0 KB |
- |
