Submission #519786

#TimeUsernameProblemLanguageResultExecution timeMemory
519786Dasha_GnedkoGift (IZhO18_nicegift)C++17
100 / 100
1591 ms269492 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/detail/standard_policies.hpp> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC target("avx2") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4") using namespace std; //using namespace __gnu_pbds; //template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>; mt19937 gen(time(0)); #define ll long long #define ld long double #define pb push_back #define F first #define S second #define TIME clock() * 1.0 / CLOCKS_PER_SEC #define sz(a) int32_t(a.size()) #define endl '\n' //#define int long long const int N = 4e6 + 100; const int M = 18; const int mod = 998244353; const int inf = 1e9 + 7; pair < ll, int > a[N]; set < pair < pair < int, int >, pair < ll, int > > > st; vector < int > ans[N]; int nxt[1000100]; int get(int i) { if (i == -1 || a[i].F) return i; return nxt[i] = get(nxt[i]); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif // LOCAL int n, k; cin >> n >> k; ll sum = 0, mx = 0; for(int i = 0; i < n; i++) { cin >> a[i].F; mx = max(mx, a[i].F); sum += a[i].F; a[i].S = i; nxt[i] = i + 1; } nxt[n - 1] = -1; if (sum % k || mx > sum / k) { cout << -1; return 0; } sort(a, a + n); reverse(a, a + n); int uk = 1; st.insert({{0, 0}, {sum / k, 0}}); vector < pair < ll, int > > ve; while (sz(st)) { pair < pair < int, int >, pair < ll, int > > p = *st.begin(); st.erase(st.begin()); int sz = p.F.F, i = get(p.F.S), numb = p.S.S; ll k = p.S.F; if (i == -1) { ve.pb({k, numb}); continue; } if (a[i].F >= k) { a[i].F -= k; ans[numb].pb(a[i].S); st.insert({{sz + 1, i + 1}, {k, numb}}); continue; } for(auto to: ans[numb]) ans[uk].pb(to); ans[uk].pb(a[i].S); st.insert({{sz, i + 1}, {k - a[i].F, numb}}); st.insert({{sz + 1, i + 1}, {a[i].F, uk}}); a[i].F = 0; uk++; } cout << uk << endl; for(auto to: ve) { cout << to.F << " "; for(auto x: ans[to.S]) cout << x + 1 << " "; cout << endl; } }
#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...