# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
89489 | 2018-12-15T06:24:54 Z | antimirage | Gift (IZhO18_nicegift) | C++17 | 537 ms | 106540 KB |
#include <bits/stdc++.h> #define pb emplace_back #define mk make_pair #define fr first #define sc second using namespace std; const int N = 1e6 + 5; int n, k, sz, l[N]; long long sum, ar[N], mx, cn, mn[N]; vector < pair <long long, int> > vec[N]; vector < vector <int> > ans; main() { cin >> n >> k; for (int i = 1; i <= n; i++) scanf("%lld", &ar[i]), sum += ar[i], mx = max(mx, ar[i]); if (mx > sum / k || sum % k != 0){ puts("-1"); return 0; } sum /= k; for (int i = 1; i <= n; i++) { if (cn + ar[i] > sum){ vec[sz].pb( make_pair(sum - cn, i) ); ar[i] -= (cn + ar[i] - sum); i--; cn = 0; sz++; } else{ cn += ar[i]; vec[sz].pb( make_pair(ar[i], i) ); } if (cn == sum){ cn = 0; sz++; } } assert(sz == k); while (1) { ans.pb( vector <int>() ); mn[ans.size()] = 2e18; for (int j = 0; j < sz; j++) mn[ans.size()] = min(vec[j][ l[j] ].fr, mn[ans.size()]); for (int j = 0; j < sz; j++) { ans.back().pb( vec[j][ l[j] ].sc ); vec[j][ l[j] ].fr -= mn[ ans.size() ]; if (vec[j][ l[j] ].fr == 0) l[j]++; } if (l[0] >= (int)vec[0].size() ) break; } cn = 0; cout << ans.size() << endl; for (auto it : ans) { printf("%lld ", mn[ cn + 1 ]); for (auto to : it) printf("%d ", to); puts(""); cn++; } } /** 4 2 2 3 3 2 **/
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 23800 KB | n=4 |
2 | Correct | 25 ms | 23808 KB | n=3 |
3 | Correct | 26 ms | 23984 KB | n=3 |
4 | Incorrect | 26 ms | 23984 KB | Taken too much stones from the heap |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 23800 KB | n=4 |
2 | Correct | 25 ms | 23808 KB | n=3 |
3 | Correct | 26 ms | 23984 KB | n=3 |
4 | Incorrect | 26 ms | 23984 KB | Taken too much stones from the heap |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 23800 KB | n=4 |
2 | Correct | 25 ms | 23808 KB | n=3 |
3 | Correct | 26 ms | 23984 KB | n=3 |
4 | Incorrect | 26 ms | 23984 KB | Taken too much stones from the heap |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 537 ms | 106540 KB | n=1000000 |
2 | Correct | 346 ms | 106540 KB | n=666666 |
3 | Correct | 199 ms | 106540 KB | n=400000 |
4 | Runtime error | 124 ms | 106540 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 23800 KB | n=4 |
2 | Correct | 25 ms | 23808 KB | n=3 |
3 | Correct | 26 ms | 23984 KB | n=3 |
4 | Incorrect | 26 ms | 23984 KB | Taken too much stones from the heap |
5 | Halted | 0 ms | 0 KB | - |