Submission #44496

#TimeUsernameProblemLanguageResultExecution timeMemory
44496nickyrioGift (IZhO18_nicegift)C++17
0 / 100
2065 ms71896 KiB
/* Condition: - Sum of arrays must be divisible by k - Maximum number must be smaller than or equal to (sum / k) Solution: - Divide array into k blocks - .... */ #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) #define FORD(i, a, b) for (int i = (a); i >= (b); --i) #define REP(i, a) for (int i = 0; i < (a); ++i) #define DEBUG(x) { cerr << #x << '=' << x << endl; } #define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; } #define N 1001000 #define pp pair<long long, int> #define endl '\n' #define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define taskname "" #define bit(S, i) (((S) >> (i)) & 1) using namespace std; int n, k; vector< vector<pp> > block; vector< vector<long long> > res; long long a[N]; int main() { #ifdef NERO freopen("test.inp","r",stdin); freopen("test.out","w",stdout); double stime = clock(); #else //freopen(taskname".inp","r",stdin); //freopen(taskname".out","w",stdout); #endif //NERO IO; cin >> n >> k; long long sum = 0, mx = 0; FOR(i, 1, n) { cin >> a[i]; mx = max(mx, a[i]); sum += a[i]; } long long average = (sum / k); if (sum % k || mx > average) { cout << -1; return 0; } vector<pp> now; long long temp = 0; FOR(i, 1, n) { temp += a[i]; if (temp >= average) { now.push_back(pp(a[i] - (temp - average), i)); block.push_back(now); temp -= average; now.clear(); if (temp) now.push_back(pp(temp, i)); } else now.push_back(pp(a[i], i)); } //REP(i, k) Arr(block[i], 0, block[i].size() - 1); while (sum > 0) { vector<long long> ans; long long subtract = 1e18; REP(i, k) subtract = min(subtract, block[i].back().first); sum -= subtract * k; DEBUG(subtract); ans.push_back(subtract); REP(i, k) { block[i].back().first -= subtract; ans.push_back(block[i].back().second); if (block[i].back().first == 0) block[i].pop_back(); } res.push_back(ans); } cout << res.size() << '\n'; REP(i, res.size()) { for (int x : res[i]) cout << x << ' '; cout << '\n'; } #ifdef NERO double etime = clock(); cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n"; #endif // NERO }

Compilation message (stderr)

nicegift.cpp: In function 'int main()':
nicegift.cpp:12:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i, a) for (int i = 0; i < (a); ++i)
                                     ^
nicegift.cpp:78:5: note: in expansion of macro 'REP'
     REP(i, res.size()) {
     ^~~
nicegift.cpp:79:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for (int x : res[i]) cout << x << ' '; cout << '\n';
         ^~~
nicegift.cpp:79:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         for (int x : res[i]) cout << x << ' '; 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...