Submission #50854

#TimeUsernameProblemLanguageResultExecution timeMemory
50854NicksechkoGift (IZhO18_nicegift)C++14
100 / 100
748 ms208224 KiB
#include <bits/stdc++.h> using ll = long long; using ld = long double; using namespace std; const int MAXN = 2000001; vector<vector<ll>> ans; vector<pair<int, ll>> g[MAXN]; ll a[MAXN]; int main() { #ifdef PAUNSVOKNO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr); int n, k; cin >> n >> k; ll s = 0; for (int i = 1; i <= n; ++i) { cin >> a[i]; s += a[i]; } if (s % k) { return cout << -1 << "\n", 0; } int cur = 0; s /= k; ll left = s; for (int i = 1; i <= n; ++i) { if (a[i] > s) { return cout << -1 << "\n", 0; } if (a[i] >= left) { g[cur++].emplace_back(i, left); if (a[i] != left) { g[cur].emplace_back(i, a[i] - left); } left += (s - a[i]); } else { g[cur].emplace_back(i, a[i]); left -= a[i]; } } while (!g[0].empty()) { ll x = (1ll << 60); ans.emplace_back(k + 1); for (int i = 0; i < k; ++i) { ans.back()[i + 1] = g[i].back().first; x = min(x, g[i].back().second); } ans.back()[0] = x; for (int i = 0; i < k; ++i) { if (x == g[i].back().second) { g[i].pop_back(); } else { g[i].back().second -= x; } } } cout << ans.size() << "\n"; for (auto& v : ans) { for (auto& t : v) { cout << t << " "; } cout << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...